You are not logged in. Please login at www.codechef.com to post your questions!

×

CHNGSUM - Editorial

1
2

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

This question is marked "community wiki".

asked 10 Jul '17, 21:38

prateekg603's gravatar image

5★prateekg603
20421223
accept rate: 0%

edited 24 Jul '17, 00:39

admin's gravatar image

0★admin ♦♦
19.8k350498541


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

link

answered 24 Jul '17, 15:37

gear4's gravatar image

6★gear4
1063
accept rate: 0%

1

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

(24 Jul '17, 15:45) dpraveen ♦♦4★

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

link

answered 24 Jul '17, 01:06

doramon's gravatar image

2★doramon
865
accept rate: 5%

edited 24 Jul '17, 01:07

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

link

answered 24 Jul '17, 09:43

bhushan_'s gravatar image

5★bhushan_
1027
accept rate: 9%

My O(nlogn) solution was giving tle.

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

link

answered 24 Jul '17, 16:06

ayush_agrawal_'s gravatar image

4★ayush_agrawal_
2614
accept rate: 11%

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

link

answered 27 Jul '17, 15:34

meth_coder's gravatar image

1★meth_coder
11
accept rate: 0%

edited 27 Jul '17, 15:36

Modulo(10^9+7), or 1000000007

(27 Jul '17, 15:35) vijju123 ♦♦5★

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) meth_coder1★

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) vijju123 ♦♦5★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,719
×2,598
×56
×4

question asked: 10 Jul '17, 21:38

question was seen: 1,985 times

last updated: 27 Jul '17, 21:41