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

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

10827 - Maximum sum on a torus

Post by sohel » Tue Mar 08, 2005 7:07 am

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

Post by .. » Tue Mar 08, 2005 7:33 am

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:
  • Please make discussion about the algorithm BRFORE posting source code.
    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

Post by ardiankp » Tue Mar 08, 2005 7:56 am

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

Post by .. » Tue Mar 08, 2005 8:04 am

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:
  • Please make discussion about the algorithm BRFORE posting source code.
    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:

Post by Yarin » Tue Mar 08, 2005 10:43 am

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

Post by .. » Tue Mar 08, 2005 10:54 am

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:
  • Please make discussion about the algorithm BRFORE posting source code.
    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
Location: Canada

Not Specified

Post by Mahmud776 » Tue Mar 08, 2005 11:12 am

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

:lol: :lol: :lol: :lol: :lol:

User avatar
filigabriel
New poster
Posts: 15
Joined: Thu Oct 16, 2003 7:43 pm
Location: M
Contact:

Post by filigabriel » Tue Mar 08, 2005 2:20 pm

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:

Post by Yarin » Tue Mar 08, 2005 3:25 pm

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

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

Post by shamim » Tue Mar 08, 2005 3:58 pm

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
Online Contest Administrator
Posts: 20
Joined: Fri Nov 30, 2001 2:00 am

hmm

Post by contest_clarificator » Wed Mar 09, 2005 2:13 am

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

Post by ardiankp » Wed Mar 09, 2005 10:06 am

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

Post by liulike » Wed Mar 09, 2005 2:19 pm

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

Post by Cosmin.ro » Wed Mar 09, 2005 4:14 pm

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

Post by rimu » Wed Mar 09, 2005 4:48 pm

you are forgetting that the minimum allowed
sub-rectangle is 1 x 1.
for input

2
-1 -2
-3 -4

your code outputs 0
but it should be -1
hope this is the only mistake
i'll be back

Post Reply

Return to “Volume 108 (10800-10899)”