Hi.
I tried to solve the second problem of INOI 2012, Table Sum with the native approach (or the bruteforce way) as I'm not able to think of any other way in which we could attempt the problem.
After looking at a few outputs, I thought there might be some kind of pattern in the output but couldn't find any.
Any aid would be very helpful as I'm preparing for INOI 2015 and have almost no experience in algorithmic programming. I started practicing almost a week after ZIO results were out :[
asked 31 Dec '14, 00:22

Hello pm1511, First of all thanks for asking this problem. I also solved this .. Solution 1: You can solve this [problem with O(N^2) time complexity as you were doing .. one updation for each pass and then checking maximum through the array in linear time .. Solution 2 : You can use advanced data structure like segment tree , sqrt decomposition to solve this problem .. which can solve this problem with O(Nlog(N)) and O(Nsqrt(N)) complexity respectively .. Solution 3 : O(N) linear time solution. I recommend you to focuss on this only .. If you can observe then see that pattern to be added is nothing but sorted order of first N natural Numbers. Same can be apply to any AP (Airthmetic Progression) It is just a matter of common difference .. Lets walk through the example to understand it better. Consider the same given in the sample test cases .. 4 7 1 6 2 Now look First step 1 : we have to add 1 2 3 4 First step 2 : we have to add 2 3 4 1 First step 3 : we have to add 3 4 1 2 First step 4 : we have to add 4 1 2 3 Each time we are rotating the previous added permutation 1 towards left . You can also see that each position will take all the values from [1,N] inclusive. and for each position in a permutation all values get incremented by 1 till the time 1 does not occur at the position . Here the first decrement take place .. What does that mean is . Look at the second position . first step : 2 second step :3 > increment third step : 4 > increment forth step : 1 > decrement You can think that the problem is reduced to > first prepared an array this way A[1]+1 , A[2]+(2) + A[3] + 3 .....................A[N]+N. our array will be (8,3,9,6) for each when you get a number 1 at a position drecrease that position value by N and increment all the values in the array by 1 and maintains maximum .. It is not getting tough. you will amazed to see a four to five line code that i will be provided at the end :P. Now how to maintain this . once you calculated the above array . you can easily answer for step 1 . Now we need to work to step 2 to step N. Second permutation will have 1 at the index N=4. 2 3 4 1 so we have 1 at the position 4. our array was (8,3,9,6) as i said decrement the position 4 by 4 and add 1 to all elements. array looks like this (9,4,10,3) = max = 10 third permutation will have 1 at the index N1. 3 4 1 2 so we have 1 at the position 3. our array was (9,4,10,3) as i said decrement the position 3 by 4 and add 1 to all elements. array looks like this (10,5,8,4) = max = 10 .. now do it for the position 2 .. yourself .. We do not need to do for each pass. Because we can update and calculate these things simultaneously .. Here is my code link .. if you find any difficulty ask me answered 31 Dec '14, 15:16
@ma5termind Thanks for putting in such a great effort to help me out. Can you please explain your code too? That would be a great help.
(31 Dec '14, 22:56)
That's a great reduction of this complex problem! :D
(26 Dec '18, 22:00)
Here is the Sqrt Decomposition Solution for the same approach, https://ideone.com/FaTfjP
(26 Dec '18, 23:49)

There is also a O(n) algorithm to solve this question. Instead of modifying all the column sums, we can decrease the one column sum by N, and then take the maximum column sum plus 1 to find the new maximum of the column sums. You can find a detailed explanation of this question at this link:
answered 31 Dec '14, 01:07
https://www.dropbox.com/s/im7sjck0z8elukk/TABLESUM.cpp?dl=0 I wrote the above code based on the O(n) algo you suggested, but I am getting WA on all except 3 test cases. Where could I be going wrong?
(31 Dec '14, 14:55)
1
Hey try this code . Where to submit this up .. http://ideone.com/vaGrJ6 I have a post full explanation below you can check and may you find it useful for you ..
(31 Dec '14, 15:22)

I insist you do it by segment trees Just make a segment tree and then call 3 updates using lazy propagation and then just call query for each n and you are done. Time complexity O(nlogn) answered 31 Dec '14, 11:09

Hello all Can anybody of you tell me where i can submit this problem .. I am unable to find Online judge where i can submit this problem . Thanx in advance . answered 31 Dec '14, 18:52
@pm1511 Can you please check this submissionon my behalf .. http://ideone.com/vaGrJ6 and tell me result ..
(31 Dec '14, 20:06)
@mhungry Well, you got a 100 ;)
(31 Dec '14, 20:37)
@mhungry Did you read the solution above first or did you solve the problem on your own?
(31 Dec '14, 20:41)
I read what is mentioned by ma5termind. Even the code is same .
(31 Dec '14, 20:54)
@mhungry Can you please explain me the code with reference to the above answer? I'm not able to match the code with what he said in the answer...
(01 Jan '15, 19:58)

I did it by your method and it still gives me TLE for the problem (2 sec+) Could you please explain my error here? Why is it going wrong?
answered 28 Jan '15, 21:26

you have not used my logic i think .. #include <bits/stdc++.h> using namespace std; #define MAXN 200005 int N,A[MAXN] ; int main() { // your code goes here cin >> N ; for(int i=1;i<=N;i++) cin >> A[i] ; for(int i=1;i<=N;i++){ A[i] += i; A[i] = max(A[i],A[i1]) ; } cout << A[N] << " " ; int cnt = 0; for(int i=N;i>1;i){ A[i] = N ; A[i] = max(A[i],A[i+1])+1 ; ++cnt ; A[i1] += cnt ; cout << max(A[i],A[i1]) << " " ; } cout << endl ; return 0; } this was my code for this problem. I can see in your code that you are using two loops . for (int i=1; i<=n; i++) { // temp=lastsum; // for (int j=0; j<n; j++) lastsum[j]+=1; lastsum[ni]=n; cout << maxScan(lastsum) << " "; } It is taking O(N^2) time whereas my approach or my code is taking only O(N) . Please have a closer look and even then if anything is not understandable to you feel free to comment . answered 29 Jan '15, 01:16

Okay so you sort it linearly each iteration and compare by removing n1 from (ni)th position. Understood. thanks! answered 29 Jan '15, 10:33

link to problem statement?
@mogers Oops, my bad.
http://www.iarcs.org.in/inoi/2012/inoi2012/inoi2012qpaper.pdf