#prefix sum

Solutions The brute force solution consists in adding the specified value to each of the given ranges and finally finding the maximum value. Evidently, the complexity of this solution is \( O(N \cdot M)\) (where \(N\) is the size of the array and \(M\) is the number of queries) which is too high to meet time constraints. A better solution is linear on N and allocates \(O(N)\) space, involving adding the specified value solely to the starting endpoint of the ranges and subtracting it from the position immediately after the ending endpoint. [Read More]

Solutions This problem is an application of Find the Maximum Difference. Basically, we need to find out the maximum difference between two numbers in the given array \(max(prices[j] - prices[i])\) with \(i<j\). The bruce force approach is quadratic and does not pass all test cases: for each element we linearly find the biggest next value. As discussed in Find the Maximum Difference, the general solution schema is the following: 1 2 3 4 5 6 7 8 9 auto currMin = INT_MAX; auto currMax = 0; for (auto i : prices) { currMin = min(currMin, i); currMax = max(i - currMin, currMax); } cout << currMax; As long as we iterate the array, currMin keeps track of the smallest element along the way. [Read More]

Solutions The solution to this problem when d=1 can be used to solve Picking Numbers as well. A linear solution consists in: computing the prefix sum of the input array keeping a window of size m counting how many times the window bounds differ by d Here is a solution in C++: 1 2 3 4 5 6 7 8 9 10 11 12 13 int n, d, m; cin >> n; vector<int> v(n+1); copy_n(istream_iterator<int>(cin), n, next(begin(v))); cin >> d >> m; partial_sum(begin(v), end(v), begin(v)); auto cnt = 0; for (auto i=0; i<=n-m; ++i) { cnt += v[i+m] - v[i] == d; } cout << cnt; The loop can be replaced with zip | map | reduce combination of patterns: [Read More]

Solutions Checking if a certain value \(x\) is suitable takes linear time. Intuitively, we have to verify if the array can be splitted into contiguous groups of sum \(x\), without remainder (empty space on the bus is not allowed). This operation consists in iteratively checking the prefix sum of the array against a cumulative value of \(x\). For example: 1 1 2 1 1 1 2 1 3 Suppose we want to the check if 3 works. [Read More]

Solutions C++ Solution very pretty much independent from the number of the stacks (just change numberOfStacks): 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 const int numberOfStacks = 3; array<int, numberOfStacks> n{}; for (auto& i : n) cin >> i; array<vector<int>, numberOfStacks> stacks; array<int, numberOfStacks> heights{}; for (auto i=0; i<n.size(); ++i) { auto& s = stacks[i]; s. [Read More]

Solutions Since we want to maximize the number of chapters, we just sort the array and pick the first chapters which sum is less than or equal to \( t \). Here is a C++ implementation: 1 2 3 4 5 6 7 8 9 10 11 12 13 int n, t; cin >> n >> t; vector<int> v(n); copy_n(istream_iterator<int>(cin), n, begin(v)); sort(begin(v), end(v)); auto cnt = 0; for (auto i=0; i<n; ++i) { if (t-v[i] < 0) break; t -= v[i]; cnt++; } cout << cnt; The solution is \( O(N \cdot logN) \). [Read More]

You are given a sequence of integers S, your task is to find a pair i,j of indices with i<j that maximizes the difference S[j]-S[i]. Note that what makes this challenge more interesting is the requirement of order, that i < j (without it you simply need to find the maximum and minimum element of S). You have to output the value of the maximum difference. Input Format An integer N followed by N space separated integers S[i] on a new line. [Read More]

Solutions Quadratic solution This Python solution by Davide Peron calculates the difference for each combination of city/station, keeps the minimum for each city and then takes only the maximum. 1 2 def flatlandSpaceStations(n, c): return max(min(abs(city - sta) for sta in c) for city in range(n)) Linear solution The problem can be solved linearly. Assume \(arr[i]=1\) if the \(i^th\) city has a space station, \(0\) otherwise. Now calculate \(c[i]\) which denotes the distance to the nearest space station on the left. [Read More]

Solutions The naive solution consists in simulating the game: until no elements are left, continuously remove the maximum element and the elements on its right. This might be simplified a bit by performing only a “logical” removal, keeping an index updated to the rightmost element still in the valid range. For example: 1 2 3 5 4 6 9 7 ^ last element in range Bob “removes” 9: 1 2 3 5 4 6 9 7 ^ last element in range It’s clear now that 7 is not in range anymore so Andy picks 6. [Read More]

Solutions This easy problem can be solved by first sorting the calories in decreasing order: 1 2 3 4 5 6 7 8 9 10 long long n; cin >> n; vector<int> v(n); copy_n(istream_iterator<int>(cin), n, begin(v)); sort(begin(v), end(v), greater<>{}); auto miles = 0ll; for (auto i=0; i<n; ++i) { miles += v[i] * (1ll<<i); } cout << miles; The zip | map | reduce pattern emerges from the code: conceptually, it’s like zipping each calory with the ith power of 2, mapping the pair with product and summing along the way: [Read More]