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

×

INOI 2012 Problem 2 TableSum

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();
}

}

asked 31 Dec '14, 00:22

pm1511's gravatar image

1★pm1511
3156
accept rate: 0%

link to problem statement?

(31 Dec '14, 00:40) mogers5★

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

http://ideone.com/vaGrJ6

link

answered 31 Dec '14, 15:16

ma5termind's gravatar image

3★ma5termind
1.7k11630
accept rate: 11%

@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) pm15111★

That's a great reduction of this complex problem! :D

(26 Dec '18, 22:00) jvjplus2★

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

(26 Dec '18, 23:49) jvjplus2★

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

link

answered 31 Dec '14, 01:07

animesh_f's gravatar image

6★animesh_f ♦
8831422
accept rate: 9%

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) sandy9992★
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) ma5termind3★

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)

link

answered 31 Dec '14, 11:09

japoorv's gravatar image

5★japoorv
29592356
accept rate: 0%

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 .

link

answered 31 Dec '14, 18:52

mhungry's gravatar image

1★mhungry
622
accept rate: 18%

@pm1511 Can you please check this submissionon my behalf ..

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

(31 Dec '14, 20:06) mhungry1★

@mhungry Well, you got a 100 ;)

(31 Dec '14, 20:37) pm15111★

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

(31 Dec '14, 20:41) pm15111★

@pm1511

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

(31 Dec '14, 20:54) mhungry1★

@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) pm15111★

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;
}
link

answered 28 Jan '15, 21:26

aalok_sathe's gravatar image

1★aalok_sathe
1724
accept rate: 0%

edited 28 Jan '15, 22:50

@aalok_sathe

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[i-1]) ;
    }

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

link

answered 29 Jan '15, 01:16

ma5termind's gravatar image

3★ma5termind
1.7k11630
accept rate: 11%

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

link

answered 29 Jan '15, 10:33

aalok_sathe's gravatar image

1★aalok_sathe
1724
accept rate: 0%

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:

×399
×75

question asked: 31 Dec '14, 00:22

question was seen: 3,628 times

last updated: 26 Dec '18, 23:49