CHNGSUM - Editorial

PROBLEM LINK

Practice
Contest

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.

\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.

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.
  • 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.

SOLUTIONS

Author’s solution can be found here.
Tester’s solution can be found here.

1 Like

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

@doramon See that for(i=1 to N) for(j=i to N) basically denotes all the sub-arrays whose starting index is i and ending index is j. Moreover, we are finding the maximum element from the generated sub-array and adding to maxSum[j] where j which is the ending index of that sub-array. Hence we can get the sum of maximum elements of all sub-arrays ending at index j.

Edit: This is through pseudo code. I think you are confused with the index i and j. Read the statements carefully.

Use stack instead of RMQ to get O(n) complexity.

3 Likes

Yes, that’s a pretty nice idea. One can see my implementation (tester’s solution) for a possible implementation of this approach.

1 Like

My O(nlogn) solution was giving tle.

https://www.codechef.com/viewsolution/14657021

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

Modulo(10^9+7), or 1000000007

Can someone look into the above code ?
It’s just like the second case as told above but wont’t work.

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.