PROBLEM LINK
CONTEST PANEL
Author: Prateek Gupta
Tester: Praveen Dhinwa
Editorialist: Prateek Gupta
DIFFICULTY
Medium
PROBLEM
Given an array of integers of length N, you need to find the summation of F(i, j, k, l) over all quadruples (i, j, k, l) such that i ≤ j < k ≤ l, where (i, j, k, l) are the indices of any of the four elements in the array. F(i, j, j, k) is defined as the product of maximum element in range$(i, j) and minimum element in range(j, k)$ for the array.
EXPLANATION
Let’s discuss solution for both smaller and bigger constraints separately so that we can slowly arrive at the intended solution.
Solution for Smaller Constraints (N <= 100)
The smaller constraint allow you to apply a normal brute force approach. This means just doing what the question tells you to do in the most un-optimal way. There is not much theory to talk about here. Looking at the pseudo code will make the things pretty much clear.
main() {
ans = 0
for ( i = 1 to N ) {
mx = 0
for ( j = i to N ) {
mx = max(mx, A[j])
for ( k = j + 1 to N ) {
mn = INFINITY
for ( l = k to N ) {
mn = min(mn, A[l])
ans += mx*mn
}
}
}
}
print(ans)
}
Overall complexity of this approach would be around O(N^{4}). Can you improve the implementation of this approach? Please give a little time and think yourself before going any further.
Solution for N <= 10^3
Let maxSum[i] denote the sum of maximum element of all subarrays ending at index i and similarly minSum[i] denote the sum of minimum element of all subarrays starting from index i. Having said that, we wish to calculate the below summation.
To make the equation more simplified, let’s define cumMinSum[i] in the following way.
Then, the first summation can be written as :-
If you see carefully, both maxSum and minSum are independent functions and can be calculated separately. Let us have a look at the pseudo code.
for ( i = 1 to N ) {
mx = 0
for ( j = i to N ) {
mx = max(mx, A[j])
maxSum[j] += mx
}
}
for ( i = N to 1 ) {
mn = INFINITY
for ( j = i to 1 ) {
mn = min(mn, A[j])
minSum[j] += mn
}
}
for ( i = N to 1 ) {
cumMinSum[i] = cumMinSum[i + 1] + minSum[i]
}
ans = 0
for ( i = 1 to N ) {
ans += mxSum[i]*cumMinSum[i + 1]
}
print(ans)
The complexity of the above approach turns out to be O(N^{2}) but still no where close to the best solution that can be achieved. This implementation turned our naive and brute force solution to semi-brute. Well, now what can be the other ways to think that will reduce the time complexity even further? Think for yourself before moving any further. It’s fine if you are not able to come up even after lots of thinking but developing a habit to think for sometime really allows you to see why you could not think of the actual solution after reading it’s editorial.
Solution for Larger Constraints(N <= 10^5)
Now, here’s a small hint.
A certain number A[x] at position x will be maximum in some contiguous subarrays starting at index ≤ x and ending at index ≥ x. So, a number at position x will only contribute to these subarrays. But, how much value will it actually add to all these subarrays?
This should be straightforward. You can find out the length (len) of the longest contiguous subarray ending at index x that has all the values ≤ A[x]. Also, find out the greatest index y such that y > x and the subarray(x + 1, y) has all values < A[x] (Not ≤ A[x], think why?) The contribution of this number at position x will affect the subarrays starting at index ≤ x and ending at position ≥ x by len*A[x]. Similarly, you can do this for each of the number in the array and you end up getting the sum of maximums of subarrays ending at that position. The same idea can be used to calculate the minimums of subarrays starting at that position and for each such position. Now, going into the implementation.
- Finding longest contiguous subarray ending at index $x$ having all values $≤ x$ This can be achieved by RMQ + binary search. Please follow [this][6] link to know more about RMQ.
- Finding the greatest index $y$ such that $y > x$ and the subarray($x + 1, y$) has all values $< A[x]$ Again, this can be solved by RMQ + binary search. It is similar to the above mentioned subproblem.
- Updating the values contributed by each position in the maximums.
For more details on the implementation, have a look at the setter or tester’s solution. Here, all the calculations are performed without considering the MOD. Do not forget to consider that while you submit the solution in practice.
SOLUTIONS
Author’s solution can be found here.
Tester’s solution can be found here.