10827 - Maximum sum on a torus

All about problems in Volume 108. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

sidky
New poster
Posts: 50
Joined: Wed Nov 06, 2002 1:37 pm
Location: Planet Earth, Universe
Contact:

Post by sidky »

possibly, that is not the case. my AC code allows empty sub rectangles, and for rimu's input, it outputs 0

Rony
New poster
Posts: 16
Joined: Wed Jun 30, 2004 6:46 am
Location: Dhaka
Contact:

10827 - Maximum sum on a torus

Post by Rony »

Hi,
Can any one check my code ? What,s wrong ? I am getting WA. Following
is my code .
Code is removed.
[Thanks.

Regards
Rony
[Depressed]
Last edited by Rony on Wed Mar 23, 2005 1:12 pm, edited 1 time in total.

Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong

Post by Cho »

hey hey, there are three threads on this topic now.
There is no way for your O(n^2) solution to get AC.
Do you know about Maximum Contiguous Subarray Problem?

Moha
Experienced poster
Posts: 216
Joined: Tue Aug 31, 2004 1:02 am
Location: Tehran
Contact:

What`s wrong with this code?

Post by Moha »

can anybody tell me what`s wrong with this code?

Code: Select all

#include<iostream>
using namespace std;
int n,mat[150][150],pre[150][150];
main()
{
     int N;
     for(cin>>N;N--;)
     {
        int f=1,m=-101;
        cin>>n;
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
            {
                  cin>>mat[i][j];
                  mat[i+n][j]=mat[i][j+n]=mat[i+n][j+n]=mat[i][j];
                  f&=mat[i][j]<0;
                  m>?=mat[i][j];
            }
           for(int i=0;i<2*n;i++)
                 for(int j=0;j<2*n;j++)
                          pre[i][j]=(i?pre[i-1][j]:0)+mat[i][j];
            int best=0;
            for(int i=0;i<n;i++)
                 for(int j=i;j<i+n;j++)
                 {
                       int p=-1,sum=0;
                       for(int k=0;k<2*n;k++)
                       {
                             sum+=pre[j][k]-(i?pre[i-1][k]:0);
                             if(sum<0)
                              {
                                       sum=0;
                                        p=k;
                               }
                          for(;(k-p>n||pre[j][p+1]-(i?pre[i-1][p+1]:0)<=0)&&p<k;p++)
                               sum-=pre[j][p+1]-(i?pre[i-1][p+1]:0);
                           if(sum<0)
                           {
                               sum=0;
                               p=k;
                           }
                           best>?=sum;
                            }
                           }
               cout<<(f?m:best)<<endl;
          }
}

L I M O N
Learning poster
Posts: 58
Joined: Wed Dec 31, 2003 8:43 am
Location: Dhaka, Bangladesh
Contact:

10827- what's the correct answer??

Post by L I M O N »

what's the correct answer ??
3
1 -1 1
-1 4 -1
2 -1 1

Answer is 5 or 4 ???

Rony
New poster
Posts: 16
Joined: Wed Jun 30, 2004 6:46 am
Location: Dhaka
Contact:

Post by Rony »

Cho wrote:hey hey, there are three threads on this topic now.
There is no way for your O(n^2) solution to get AC.
Do you know about Maximum Contiguous Subarray Problem?
Hi,
Cho, I dont know about Maximum Contiguous Subarray Problem. Can you
help me?


Regards
Rony.

Thanks.

Cosmin.ro
Learning poster
Posts: 95
Joined: Thu Aug 21, 2003 12:02 am

Post by Cosmin.ro »

http://www.darkridge.com/~jpr5/archive/alg/node99.html, maybe you'll find a better page ... remember google is your friend.

shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

Post by shamim »

Apparently 5 is better than 4:wink:
The whole grid is also a submatrix of itself.

L I M O N
Learning poster
Posts: 58
Joined: Wed Dec 31, 2003 8:43 am
Location: Dhaka, Bangladesh
Contact:

10827-WA

Post by L I M O N »

now, in this example :
what's the correct answer??
3
1 -5 1
-5 4 -5
2 -5 1

my solution gives 5.
is it correct??
it get WA again and again.

Rony
New poster
Posts: 16
Joined: Wed Jun 30, 2004 6:46 am
Location: Dhaka
Contact:

Re: WA 10827

Post by Rony »

Rony wrote:Hi,
Can any one check my code ? What,s wrong ? I am getting WA. Following
is my code .
Code is Removed.
Thanks.

Regards
Rony
[Depressed]

chuan
New poster
Posts: 2
Joined: Fri Jul 08, 2005 5:36 pm

Post by chuan »

I have solved the problem 108 (in 0.5XXX sec).
Make some slight modification on the souce code, however, get TLE on this problem.

I think my algo takes O(n^4) at worst case.

Can anyone help?

I can explain my algo in a simple way follows:

1. The method to find maximum sum in array is same as 108,
however, since it is circularity, I appled the algo n times to find the max.
Thus get O(n^2) here.
2. Find all possible combination of rows in circularity manner.
Also take O(n^2).

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

no %

Post by sohel »

O(n^4) should pass the time limit..
.. it should take 5/6 seconds..

I haven't seen your code, but do not use any modular operations..
Look at the very first post of this thread.. I got TLE using that approach but after removing the '%', I got AC.

chuan
New poster
Posts: 2
Joined: Fri Jul 08, 2005 5:36 pm

Post by chuan »

I have solved this problem in O(n^3).
Thanks anyway.
More detail can refer to link follows:
http://acm.uva.es/board/viewtopic.php?t ... 29d16d017f
Last edited by chuan on Fri Jul 22, 2005 6:01 pm, edited 1 time in total.

Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Post by Sedefcho »

Let me also get involved in the discussion.

I solved problem 108 just a week ago so when I saw this
problem I decided to modify slightly my code of 108 and
use it for this problem.

1) How do I handle circularity ?
Well, let's say we are given the matrix(torus) A[N][N].
I just keep it in a bigger table ( 4 times bigger )
X[2*N][2*N] where

Code: Select all

X[i][j] = X[i+N][j] = X[i][j+N] = X[i+N][j+N] = A[i][j] 
for each 0<=i,j<N
2) Now one more thing - for 108 I use the algorithm of cyfra
http://acm.uva.es/board/viewtopic.php?p=2709#2709
The most interesting part in it is that in a second table B[][]
we keep the sums of all sub-rectangles of A whose top left corner
is at (0,0). That means B[j] = Sum(A[s1][s2]), where
0<=s1<=i , 0<=s2<=j.

3) Then I just use the table B and an O(N^4) algorithm to give the
answer ( to find the maximal sum ).

The problem is that I get TLE although all people here say that
we should normally get ACC if we use an O(N^4) algorithm.

Any ideas will be appreciated.

sidky
New poster
Posts: 50
Joined: Wed Nov 06, 2002 1:37 pm
Location: Planet Earth, Universe
Contact:

Post by sidky »

In the actual contest, I solved this problem with an O(n^3) approach. But before that, my team mate tried an O(n^4) approach, and got TLE. Later we found out that, other teams solved it in O(n^4). The only thing that were different from their code was that, my team mates code had higher constant factor. He had an extra loop for some checking, and that gave him TLE. Please check your constant factors. That might be the reason for your TLE.

Post Reply

Return to “Volume 108 (10800-10899)”