10827 - Maximum sum on a torus
Moderator: Board moderators
10827 - Maximum sum on a torus
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]
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.
What`s wrong with this code?
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;
}
}
-
- Learning poster
- Posts: 58
- Joined: Wed Dec 31, 2003 8:43 am
- Location: Dhaka, Bangladesh
- Contact:
10827- what's the correct answer??
what's the correct answer ??
3
1 -1 1
-1 4 -1
2 -1 1
Answer is 5 or 4 ???
3
1 -1 1
-1 4 -1
2 -1 1
Answer is 5 or 4 ???
http://www.darkridge.com/~jpr5/archive/alg/node99.html, maybe you'll find a better page ... remember google is your friend.
Re: WA 10827
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]
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).
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).
no %
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.
.. 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.
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
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.
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
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.
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
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.
-
- New poster
- Posts: 50
- Joined: Wed Nov 06, 2002 1:37 pm
- Location: Planet Earth, Universe
- Contact:
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.