×

# CONTEST PANEL

Author: Prateek Gupta
Tester: Praveen Dhinwa
Editorialist: Prateek Gupta

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$

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

20421223
accept rate: 0%

19.8k350498541

 3 Use stack instead of RMQ to get $O(n)$ complexity. answered 24 Jul '17, 15:37 6★gear4 106●3 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)
 0 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 2★doramon 86●5 accept rate: 5%
 0 @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. answered 24 Jul '17, 09:43 5★bhushan_ 102●7 accept rate: 9%
 0 My O(nlogn) solution was giving tle. https://www.codechef.com/viewsolution/14657021 answered 24 Jul '17, 16:06 261●4 accept rate: 11%
 0 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 1●1 accept rate: 0% 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)
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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