#prefix sum

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 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]

Given two unsorted arrays arr1 and arr2 - possibly containing duplicates - for each element in arr1 print the number of elements less than or equal to it in array arr2. Input Format The first line contains an integer N. Two lines follow: the first array: N space-separated elements the second array: N space-separated elements Constraints N and M are at most 100'000 Each array element is at least 0 and at most 100'000. [Read More]

You are given an array of integers A and you will be asked to answer some queries. Each query is in the form: 1 i j And you have to return the paity (Odd/Even) of sum of absolute values from A[i] to A[j], that is: 1 A[i] + A[i+1] + ... + A[j] Input Format First Line of Input contains N and Q separated by space. Next Line contains N space separated integers. [Read More]