10827 - Maximum sum on a torus

[sidky]

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

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

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

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]

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

Answer is 5 or 4 ???

[Rony]

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]

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

[shamim]

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

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

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]

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]

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]

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

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

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.