I have been trying to solve a problem where i needed to find the sum of the minimum of all the subarrays of an array. If someone know of an O(N) algorithm to such problem. Thanks.
# | User | Rating |
---|---|---|
1 | tourist | 3993 |
2 | jiangly | 3743 |
3 | orzdevinwang | 3707 |
4 | Radewoosh | 3627 |
5 | jqdai0815 | 3620 |
6 | Benq | 3564 |
7 | Kevin114514 | 3443 |
8 | ksun48 | 3434 |
9 | Rewinding | 3397 |
10 | Um_nik | 3396 |
# | User | Contrib. |
---|---|---|
1 | cry | 167 |
2 | Um_nik | 163 |
3 | maomao90 | 162 |
3 | atcoder_official | 162 |
5 | adamant | 159 |
6 | -is-this-fft- | 158 |
7 | awoo | 155 |
8 | TheScrasse | 154 |
9 | Dominater069 | 153 |
10 | nor | 152 |
I have been trying to solve a problem where i needed to find the sum of the minimum of all the subarrays of an array. If someone know of an O(N) algorithm to such problem. Thanks.
Name |
---|
Click
You can see a similar problem Here . Check out it's editorial for solution details.
The first idea that comes to mind is an O(NlogN) algorithm to solve it, which is worse than O(N) but by a small margin.
Let x be the smallest element in the array and i be its index in the array (starting from 1). It's not hard to see that the amount of subarrays that contain x is equal to i*(N+1-i), where N is the index of the last element, and obviously the minimum of all these subarrays is x, so we can add x*i*(N+1-i) to the answer. Now, for every other y in the array, y cannot be the minimum for any subarray that contains x. So, we can split our array in two arrays [1,i-1] and [i+1,N] and solve the problem recursively, summing up the partial results in the end. Don't forget to fix the indexes at every step of the algorithm (the values for i and N will change depending on the current sub-array) At each step we have to find the minimum (this step will take O(logN) if you use a segment tree) and we have exactly N steps because at each step we remove one element from the array, so the final complexity is O(NlogN). If you choose to use sparse table instead of segment tree to perform the min queries, you can get min queries in O(1) but the cost to build the table is O(NlogN) so in the end of the day its all the same.
If you are confused i coded this: http://code.geeksforgeeks.org/paP9K7
Yes, it can be done in O(n).
For each position i, find the nearest element to its right whose value is less than that at i (if such element does not exist, consider this parameter to be n+1, where n is size of array). This whole process can be done in O(n) using stack.
Now start processing the array from right to left. Let DP[i] denote the sum of minimum of subarrays [i, j] such that i <= j <= n. Assume you are currently processing position i and the value of the above parameter is p. For all subarrays [i, j] such that i <= j < p, the minimum will be arr[i]. And for all subarrays [i, j] such that p <= j <= n, the sum of minimum of these subarrays has already been computed and stored in DP[p].
So, your formula becomes: DP[i] = (p-i)*arr[i] + DP[p]
UPD: This is the exact same problem, from a recent contest.
My code for the same can be found here.
I solved this problem using DSU, which isn't exactly O(N) but it's very efficient nevertheless. If we add elements in reverse order (from largest to smallest), we can keep blocks of already added contiguous elements using DSU. If current block goes from l to r and we just added Ai, then we must add to the answer (i - l + 1) * (r - i + 1) * Ai (all sub-blocks having Ai as minimum).
Didn't understand. Code snippet please!
Yes, sure. Here's the code -> Sum of all subarrays minimums
Further explanation of the solution: If current block goes from l to r, it means that Al - 1 and Ar + 1 are smaller than the current element, because we're adding elements from largest to smallest. This means any subarray containing either Al - 1 or Ar + 1 won't have Ai as minimum element, so all subarrays that will have Ai as minimum will be completely contained within the current block (and have to include Ai obviously). If subarray goes from p to q, we need p ≤ l and q ≥ r, so we have i - l + 1 possible positions for p and r - i + 1 possible positions for q, that's why we have to add (i - l + 1) * (r - i + 1) * Ai to the answer.
Thank you! Don't you think it's better to put code in spoiler style, so that code and explanation are close together? :)
It might be a good idea, I will consider it!
I was wondering how can these problem be solved.
Thanks in advance!
I can answer the first question for now.
Average of a subarray [l, r] can be expressed as . From this, we can see that if element Ai appears at x subarrays of size s, then this will contribute to the final answer with .
Now the problem reduces to "how many times does each element appear at some subarray of size s for every size s in the range [1, N]?. We need to calculate the matrix of occurrences and we're done. This matrix, for N = 7 for example, will look as follows...
The same will apply for bigger sizes as well. Column i will be equal to column i - 1 but with range [i, N - i + 1] increased by 1. This can be achieved in linear time with prefix sums. Let and Fi be the contribution of element Ai to the final answer (divided by Ai). Initially F1 = FN = SN, then for every i we perform the assignment Fi = Fi - 1 + SN - i + 1 - Si - 1 if i is in the first half of the array or Fi = Fi - 1 + Si - SN - i if i in the second half of the array. This last bit can be done easily with two pointers, incrementing one and decrementing the other.
Here's the code for the solution: Sum of averages
Looks good!! Thanks!
Thanks a lot for everyone for their great and smart solutions.
To keep you updated after thinking i found this O(n) solution that uses a Stack. It's based on counting the number along with every index as long as the value in the current index is great than it's value and when the current value is below the value in the stack i start removing from the stack.
Can you explain the solution?
Here is an explanation.