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 » Thu Mar 10, 2005 6:31 am

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 » Thu Mar 10, 2005 3:03 pm

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.

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

Post by Cho » Thu Mar 10, 2005 3:41 pm

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 » Thu Mar 10, 2005 4:01 pm

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 » Sun Mar 13, 2005 7:47 am

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 » Sun Mar 13, 2005 10:11 am

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 » Sun Mar 13, 2005 10:55 am

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

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

Post by shamim » Sun Mar 13, 2005 1:16 pm

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 » Mon Mar 14, 2005 6:43 am

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 » Wed Mar 23, 2005 1:11 pm

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 » Fri Jul 08, 2005 6:01 pm

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

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

no %

Post by sohel » Sat Jul 09, 2005 8:59 am

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 » Mon Jul 11, 2005 5:47 am

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.

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

Post by Sedefcho » Fri Jul 15, 2005 7:09 pm

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 » Sat Jul 16, 2005 3:11 pm

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)”