PROBLEM LINKCONTEST PANELAuthor: Prateek Gupta DIFFICULTYMedium PROBLEMGiven 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. EXPLANATIONLet'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 unoptimal way. There is not much theory to talk about here. Looking at the pseudo code will make the things pretty much clear.
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^3Let $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. $$\displaystyle\sum_{i=1}^{N  1} maxSum[i]*(minSum[i + 1]\ +\ minSum[i + 2]..\ +\ minSum[N])$$ To make the equation more simplified, let's define $cumMinSum[i]$ in the following way. $$cumMinSum[i] = \displaystyle\sum_{j=i}^{N} minSum[j]$$ Then, the first summation can be written as : $$\displaystyle\sum_{i=1}^{N  1} maxSum[i]*(cumMinSum[i + 1])$$ 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.
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 semibrute. 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.
Again, this can be solved by RMQ + binary search. It is similar to the above mentioned subproblem. $$maxSum[x] += (len*A[x])$$ $$maxSum[y + 1] = (len*A[x])$$ 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. SOLUTIONSAuthor's solution can be found here.
This question is marked "community wiki".
asked 10 Jul '17, 21:38

for ( i = 1 to N ) { mx = 0 for ( j = i to N ) { mx = max(mx, A[j]) maxSum[j] += mx } } explain this how it is calculating maxSum[i]=sum of maximum element of all subarrays ending at index i answered 24 Jul '17, 01:06

@doramon See that Edit: This is through pseudo code. I think you are confused with the index i and j. Read the statements carefully. answered 24 Jul '17, 09:43

My O(nlogn) solution was giving tle. answered 24 Jul '17, 16:06

Is it Modulo(10^9)+7 or Modulo(10^9+7) ? This code is giving wrong answer for all the subtasks. https://www.codechef.com/viewsolution/14684306 answered 27 Jul '17, 15:34
Modulo(10^9+7), or 1000000007
(27 Jul '17, 15:35)
Can someone look into the above code ? It's just like the second case as told above but wont't work.
(27 Jul '17, 21:20)
It must be overflow. Why is your answer variable declared int? Say, max[i] and currmin[i+1] both are 10^9, that will mean int ans=(ans+10^18) and it will immediatetly overflow and give WA.
(27 Jul '17, 21:41)
