10827 - Maximum sum on a torus

[emotional blind]

ha ha I got accepted and ranked 2 in this problem with timing 0:00.230

[albet_januar]

i got TLE for this problem..
i really confuse bout the O( n^3 ), can anybody help me??

Code: Select all

Deleted

[Jan]

Your complexity is O(n^4). It can be solved in O(n^3).

[albet_januar]

any idea for doing O( n^3 )??

i don't have idea..

[shamim]

Before solving this problem, you need to know how to solve problem 108.

Assuming you have solved it, there are two possibilites for the maximum sum.
One is the simple case when the maximum occurs without any wrapping.
The other case is when, there is wrapping.
In the second case, change the sign of the numbers and find then find the maximum. So, the answer will be the part not formed by this maximum.
Anyway, there is another post which visually displays it.
Take a look into that also.

[albet_januar]

i had solve prob 108.. i use o(n^4)
i cannot think bout the o(n^3) algorithms..

[forthright48]

Before solving this problem, you need to know how to solve problem 108.

Assuming you have solved it, there are two possibilites for the maximum sum.
One is the simple case when the maximum occurs without any wrapping.
The other case is when, there is wrapping.
In the second case, change the sign of the numbers and find then find the maximum. So, the answer will be the part not formed by this maximum.
Anyway, there is another post which visually displays it.
Take a look into that also.

I tried by eliminating the smallest rectangle to get the wrap value. But then I realized, this method cannot handle case like:

Code: Select all

1
3
 100 -100  100
-100 -100 -100
 100 -100  100

The answer is 400. We wrap only the four corner into a rectangle.

I tried running a normal two pointer. Each time I check if the difference between the two pointer is > n or not? Sadly this failed too.

I got AC using n^4 complexity. But this thing is bugging me. Exactly how do I pull of n^3 and maintain the wrapping? In normal two pointer, if sum gets less than 0, we pull the left pointer forward. But here, in order to get maximum, we sometimes need to pull the left pointer even when our sum is positive.

For example, we have a linear array with n = 5
8 -2 1 -3 8

Without wrapping the answer is 12. With wrapping 16.

Now if we want to wrap, things progress like this:
8 -2 1 -3 8 //I have this for now
-2 1 -3 8 8 //In order to take new 8, I had to leave first number. Sum still 12
1 -3 8 8 -2 //Now to take next number I leave the -2 behind. Sum still 12.

Then I realized, the sum will be constant from now. So I decided to pull my left pointer if its pointing to a negative number. So the progression becomes
8 -2 1 -3 -8
-2 1 -3 8 8
1 -3 8 8 // Pulled my left pointer to leave behind negative number. But the next number is 1. So I don't pull it further. Sum is now 14.
1 -3 8 8 -2 // Sum is once again 12

This approach failed too. So how exactly do I decide when to pull my left pointer?

[brianfry713]

Duplicate the original N by N matrix to a 2 * N by 2 * N matrix and then run Kadane’s algorithm.