10827 - Maximum sum on a torus

[sohel]

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

[..]

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.

[ardiankp]

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

[..]

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!

[Yarin]

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.

[..]

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.

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

[Mahmud776]

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]

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

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]

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]

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]

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]

Can anybody explain any O (n^3) solution ???

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]

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]

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]

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