## 10827 - Maximum sum on a torus

Moderator: Board moderators

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

### 10827 - Maximum sum on a torus

Is there a O(n^3) solution for this..
.. my algo is O(n^4) and it gets TLE.

the body looks somthing like this

Code: Select all

``````for(i=0;i<N;i++) {
for(j=0;j<N;j++)
C[j] = 0;
cnt = 0;
for(j=i;cnt<N;cnt++, j = (j +1) % N ) {
for(k=0;k<N;k++)
C[k] += A[j][k];
linear();
}
}
``````
where the linear array takes n^2 time to find the max sum of its contents.

the worst case is something like O(18 * 75 * 75 * 75 * 75 ) =
O(569531250)..
.. shouldn't this pass the time limit.

What is more strange, is that some of my friend applied O(N^4) time and got AC in the real time contest( not online but in a local contest ).

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong
My AC code is O(n^4), it passes the online contest time limit with a runtime of 0.9x second.

This problem is a "circular" version of 108. At first I try to modify the O(n^3) algorithm for 108, but on the key part I can't find linear algorithm. At last I used an O(n^2) algorithm with some cut off for that part and get AC.
My signature:
We can learn much more in discussion than reading source code.
• I HATE testing account.
• Don't send me source code for debug.

ardiankp
New poster
Posts: 27
Joined: Mon Nov 01, 2004 4:04 pm
Can use exactly same algo with 108.

the circular can be solved by substracting the total of that column with minimum sum between row 1..n-2 -> therefore O(n^3)

Anyway dunno whether my approach in 108 is same with yours....

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong
ardiankp wrote: the circular can be solved by substracting the total of that column with minimum sum between row 1..n-2 -> therefore O(n^3)
Oh yes, that's a good idea, thanks!
My signature:
We can learn much more in discussion than reading source code.
• I HATE testing account.
• Don't send me source code for debug.

Yarin
Problemsetter
Posts: 112
Joined: Tue Sep 10, 2002 5:06 am
Location: Ume
Contact:
This is most annoying. You are NOT supposed to pass with a N^4 algorithm. I'm not sure what has happened to the time limit, it should be 1 second or so.

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong
Yarin wrote:I'm not sure what has happened to the time limit, it should be 1 second or so.
In the online contest, the time limit is 1 second and I passed it with O(n^4), although its runtime is 0.93s. Normally every problem that is added to online judge after contest will have time limit 10seconds. If you feel unhappy about that, you can write to the judge and ask them to restore the time limit.
Yarin wrote:You are NOT supposed to pass with a N^4 algorithm.
I think one of the most interesting thing in writting problem is, you can't forsee how other people will solve it. Every person will use his own method to get AC. If a problem has one and only one method to get AC, I think that this problem is boring......... If a people can get AC with an algorithm of higher complexity, there must be some great optimization behind, why can't we try to appreciate that effort??
My signature:
We can learn much more in discussion than reading source code.
• I HATE testing account.
• Don't send me source code for debug.

Mahmud776
New poster
Posts: 22
Joined: Mon Dec 22, 2003 9:29 am

### Not Specified

Hello:
I also got accepted with O(n^4) complexity.
Although my solution could not pass the time limit of 1 sec in online contest,but I got accepted in this problem in offline with time(6.670 sec) .

filigabriel
New poster
Posts: 15
Joined: Thu Oct 16, 2003 7:43 pm
Location: M
Contact:
My programs runs is O(n^3) best case and O(n^4) in worst case.

It runs in 1.059 seconds.

Can anybody explain any O (n^3) solution ???
ardiankp wrote: the circular can be solved by substracting the total of that column with minimum sum between row 1..n-2 -> therefore O(n^3)
Maybe I am not a good english reader, but I dont understand previous quote.

Yarin
Problemsetter
Posts: 112
Joined: Tue Sep 10, 2002 5:06 am
Location: Ume
Contact:
.. wrote:
Yarin wrote:I'm not sure what has happened to the time limit, it should be 1 second or so.
In the online contest, the time limit is 1 second and I passed it with O(n^4), although its runtime is 0.93s. Normally every problem that is added to online judge after contest will have time limit 10seconds. If you feel unhappy about that, you can write to the judge and ask them to restore the time limit.
If you managed to get the n^4 algo to run that fast, I guess AC is ok. In any case, it's very hard to forsee all possible pruning conditions. I would have wanted to increase n to 100 or 200, except that the I/O part becomes too intensive then which ain't good.

I wasn't aware that the time limit was different in the online contests and after the contest. That doesn't really make sense, since the problem is so much easier (read: boring) if you're given 10 seconds instead of 1. A lot of people will solve it (or think they did) without effort after the contest, and not be challenged at all.

shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA
Yarin, maybe it is better that you generate many more cases and send it to the judge. That way, ineffcient codes won't even pass the 10 sec time limit.

contest_clarificator
Posts: 20
Joined: Fri Nov 30, 2001 2:00 am

### hmm

Yarin wrote:
If you managed to get the n^4 algo to run that fast, I guess AC is ok. In any case, it's very hard to forsee all possible pruning conditions. I would have wanted to increase n to 100 or 200, except that the I/O part becomes too intensive then which ain't good.

I wasn't aware that the time limit was different in the online contests and after the contest. That doesn't really make sense, since the problem is so much easier (read: boring) if you're given 10 seconds instead of 1. A lot of people will solve it (or think they did) without effort after the contest, and not be challenged at all.
Yes that is the rule that UVa always follow, although I don't fully agree with it. So for my time sensitive problems I regenerate larger judge data (increase number of test case but don't change range so that same solution works). I think I will also have to regenerate judge data for problem E (of last contest). But first I will change the time limits (if technically possible).

-Shahriar

ardiankp
New poster
Posts: 27
Joined: Mon Nov 01, 2004 4:04 pm
filigabriel wrote:Can anybody explain any O (n^3) solution ???
ardiankp wrote: the circular can be solved by substracting the total of that column with minimum sum between row 1..n-2 -> therefore O(n^3)
Maybe I am not a good english reader, but I dont understand previous quote.
Have you solved the problem 108?
My method is to find all possible summation for each row, and find the maximum combination for the row (become 1 dimension problem)

But because of circularity, the maximum sum can be reached not only by that way, but also by substracting total value with minimum value.

Example: (1 dimension)
2 -3 1 5
max sum = 6
min sum = -3
total = 5
result = max( 6, 5-(-3)) = 8

liulike
Learning poster
Posts: 52
Joined: Wed Jul 30, 2003 10:56 am

### 10827 maximum sum on a torus WAing

I got wa again and again for this problem.
Here is my I/O
Are they correct?
Thanks everyone!
Input:

Code: Select all

``````12
2
-1 1
1 -1
5
1 2 4 3 -3
-1 3 1 -2 2
0 -2 -1 1 4
0 -3 5 -3 1
-4 2 0 2 -4
4
1 0 0 1
0 -1 -1 0
0 4 -1 0
1 0 0 2
2
-2 -5
-4 -3
1
-10
2
-2 -3
-4 -5
1
-10
1
1000

5
1 -1 0 0 -4
2 3 -2 -3 2
4 1 -1 5 0
3 -2 1 -3 2
-3 2 4 1 -4
5
1 2 4 3 -3
-1 3 1 -2 2
0 -2 -1 1 4
0 -3 5 -3 1
-4 2 0 2 -4
2
1 2
3 4
5
1 -1 0 0 -4
2 3 -2 -3 2
4 1 -1 5 0
3 -2 1 -3 2
-3 2 4 1 -4
3
1 2 3
4 5 6
7 8 9

``````
Output:

Code: Select all

``````1
15
9
0
0
0
0
1000
15
15
10
15``````

Cosmin.ro
Learning poster
Posts: 95
Joined: Thu Aug 21, 2003 12:02 am
You could test that yourself with an O(n^6) brute force algo. I tested your input with my AC program and you have 13 tests in your input instead of 12 and also for the matrices with only negative values the result isn't 0.

rimu
New poster
Posts: 9
Joined: Sat Feb 26, 2005 4:41 pm
you are forgetting that the minimum allowed
sub-rectangle is 1 x 1.
for input

2
-1 -2
-3 -4