INOI 2012 Problem 2 TableSum

general
,
1

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 :[

Here is my code (its in java, sorry about that):



        import java.io.*;
        import java.util.Scanner;

        public class TABLESUM {
	
	public static Scanner in = new Scanner(System.in);
    
	public static PrintWriter pw = new PrintWriter(System.out);
	public static void main(String[] args) throws IOException {
		
		int n = in.nextInt();
		int[] ar = new int[n];
		int[] def = new int[n];
		
		 
		
		for (int i = 0;  i < n; i++) {
			ar[i] = in.nextInt();
		}
		for (int i = 0; i < n ; i++) {
			def[i] = i+1;
		}
		
		for (int i = 0; i < n; i++) {
			tableSum(ar, def);
			nextPerm(def);
		}
	}
	public static int[] nextPerm (int[] a) {
		int first = a[0];
		for (int i = 0; i < a.length; i++) {
			if (i == a.length-1) {
				a[i] = first;
			}else {
			a[i] = a[i+1];
			}
		}
		return a;
	}
	
	public static void tableSum (int[] a, int[] b) {
		int max = 0;
		for (int i = 0; i < a.length; i++) {
			if (a[i] + b[i] > max) {
				max = a[i] + b[i];
			}
		}
		pw.print(max + " ");
		pw.flush();
	}
}
2

link to problem statement?

3

@mogers Oops, my bad.

4

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.
So we only need to update one column instead of all of them.

You can find a detailed explanation of this question at this link:

Table Sum

1 Like
5

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)

6

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?

7

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

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

6 Likes
8

Hey try this code . Where to submit this up …


I have a post full explanation below you can check and may you find it useful for you …

1 Like
9

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 .

10

@pm1511
Can you please check this submissionon my behalf …

http://ideone.com/vaGrJ6 and tell me result …

11

@mhungry Well, you got a 100 :wink:

12

@mhungry Did you read the solution above first or did you solve the problem on your own?

13

@pm1511

I read what is mentioned by ma5termind. Even the code is same .

14

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

15

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

16

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?

#include <iostream>
#include <vector>
#define big unsigned long long int
using namespace std;
/* code */
big maxScan(vector <big> noob)
{
	ios_base::sync_with_stdio(false);
	big maxn=0;
	for (int y=0; y<noob.size(); y++)
		if (noob[y]+1>maxn) maxn=noob[y];
	return maxn;
}

int main()
{
	ios_base::sync_with_stdio(false);
	big n;
	cin>>n;
	vector <big> nums, lastsum;
	for (int i=0; i<n; i++)
	{
		big l; cin>>l; lastsum.push_back(i+1+l);
	}
		
//	vector <big> nat;
//	for (int i=0; i<n; i++)
//		nat.push_back(i+1);
//	vector <big> lastsum;
//	for (int i=0; i<n; i++)
//		lastsum.push_back(i+1+nums[i]);
	vector <big> temp;
	for (int i=1; i<=n; i++)
	{
//		temp=lastsum;
//		for (int j=0; j<n; j++) lastsum[j]+=1;
		lastsum[n-i]-=n;
		cout<<maxScan(lastsum)<<" ";
		
	}
	
	return 0;
}
17

@aalok_sathe

you have not used my logic i think …

#include 
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[i-1]) ;
	}
	
	cout << A[N] <1;i--){
		
		A[i] -= N ;
		A[i] = max(A[i],A[i+1])+1 ;
		++cnt ;
		A[i-1] += cnt ;
		cout << max(A[i],A[i-1]) << " " ;
	}
	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[n-i]-=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 .

18

Okay so you sort it linearly each iteration and compare by removing n-1 from (n-i)th position.
Understood. thanks!

19

That’s a great reduction of this complex problem! :smiley:

20

Here is the Sqrt Decomposition Solution for the same approach, https://ideone.com/FaTfjP