Can anyone discuss their approach for this question ?
2 Likes
Hint: For each element in each array, determine the range in which they are the maximum number. This can be accomplished in linear time using a stack.
2 Likes
Thanx that you provided hint…now i can think some more.
I did this using stock span, but after that I couldn’t figure out O(n) method to calculate all the values. Could you give some hint.
@domhieu : I figured out that we can determine the range in which an element is maximum but couldnt figure out what to do next. I meant how to calculate the contribution of the element for each K ?
for example if the array is 5 4 3 2 1 : contribution of 5 is 1 for every K(1<=K<=5), if the array was 4 5 3 2 1 contribution becomes 1 2 2 2 1, if the array was 1 2 5 4 3 contribution becomes 1 2 3 2 1 . Is there some pattern I am missing ?
1 Like
@sarvagya3943 You’re heading in the right direction. Be careful calculating how many times an element contribute to a particular K though - it’s not necessarily 1 for every possible value of K. After that you might detect some pattern in which the use of a range-updating scheme might come in handy. I spent almost 2 days cracking, debugging and optimizing this problem and thoroughly enjoyed every aspect of it. Problem solving at its finest ! (y)
What was the real difference between the subtasks, other than the constraint on N.
My solution was in O(n) , but did not pass 2nd sub task.
@vibhor3gupta , mine solution is quite similar to yours. You got WA on some test cases because of overflow issues. Solution 1 which is similar to yours also gave me 40 points instead of the algorithm being O(n) due to overflow issues. But once after correcting the overflow issues, Solution 2 passed for 100 points.
Glitch in your code:
Since you are using prefix sum, the number you are adding in each iteration can be either positive or negative, also the limit of number being added or subtracted is unknown.
To correct this in your code add the lines
while (ak[i] <= 0)
a[i] += MOD;
if (ak[i] >= MOD)
a[i] %= MOD;
Similarly for array “bk”.
Also, the bigger glitch was regarding the modified array “a” and “b” which you formed.
a[i] += i; was fine, but you took mod with it which may have altered the values of a[i] desired, i.e. changing the maximum values affecting for array “l” and “r” and finally your answer.
(Example a[10^4] = 10^9 + 10^4; but once you take mod, it’s value decreases and it may not be detected in the desired window size for addition to array “ak”.
Here is a bit modified version of your code which passes for 100 points. Modified Code for AC
2 Likes
You can use spare table and range minimum query approach to get maximum on interval. And after smart approach you can skip half of an array while pre compute partial sums to get final answer. After all you will get something close to O(n * log n)
Here is my solution. https://www.codechef.com/viewsolution/9390323
1 Like
Thanks for the clarification @likecs but overflow was never an issue ,the only issue was modifying the array A and B , before computing the ranges.
1 Like
@likecs
Hey, If you could just explain what each of these lines signifies and what exactly it is that you are holding in your array k, it would be a great help.
k[1] += b[i];
k[m + 2] -= b[i];
k[diff - m + 1] -= b[i];
k[diff + 2] += b[i];
Thanks! 
I solved this problem using Stack and Range updating with Fenwick Tree.
The approach was like this:
For both arrays , calculate these variations :
A=[4,1,9] , asum[k=1]=14
A=[4,9] , asum[k=2]=13
A=[9] , asum[k=3]=9
Means , for each value of k , we have to find sum of max of each window of size = k;
Then, do this for array B[] , like this:
B=[3,4,1] , bsum[k=1]=8
B=[4,4] , bsum[k=2]=8
B=[4] , bsum[k=3]=4
Now, finding the answer is very easy :
For k=1 , cout<<asum[1]*bsum[1];
For k=2 , cout<<asum[2]*bsum[2];
For k=3 , cout<<asum[3]*bsum[3];
Problem is solved.
To calculate asum[] and bsum[] arrays , the process is like this:
For each element in A[] , find next greater element to its left and right . In this range ,this
number is maximum. So , we will add this number to all possible ranges made by this interval
(Using Fenwick tree).
1 Like
I’ll start with breaking down the original problem:
-
[C] = [A(+i)](nx1)vert x [B(+j)](1xn)hori
So, change the input A and B matrices accordingly. -
Consider max of each sub-range in each of the matrices (new A and B). Lets say, at the moment, we are talking about sub-ranges of length k. Now, each max of sub-range of length k in matrix A will be multiplied to each max of sub-range of length k in matrix B to contribute to the sum required for that k (kxk matrix in C).
The Solution (Do for both A as well as B):
- Find span (left-index and right-index after which a greater value occurs) of each element (ith) of the matrix. Can be done using stacks in O(n) complexity. Prepare a field contri-max as right-index - left-index + 1. Prepare another field limit as min(i - left-index, right-index - i).
- Now, observe that the ith element’s contribution to sub-range of length 1 (ie k=1) is 1, sub-range of length 2 is 2… until sub-range of length limit; then it has a constant contribution uptil sub-range of length contri-max - lim; and then it has a linearly decreasing contribution (to 1) till sub-range of length contri-max. (Work out some examples). This also can be achieved in O(n) complexity by applying the marking algorithm (cannot come up with a better name :p) for adding a constant sum (here, the ith element) from Li to Ri.
Note: After marking the ranges for all elements, perform the summation operation twice to achieve the increasing/decreasing behavior.
Lets say we created two arrays of length n, namely incre-a for A and incre-b for B in the above process. Now, the multiplication of ith element of incre-a with ith element of incre-b is the solution for all ixi sub-matrices of C (ie F according to the question).
Handle the equality cases in Step 1 of the solution. Do all required operations in modular arithmetic.
Link for not so good code: link text