## 10827 - Maximum sum on a torus

Moderator: Board moderators

emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Contact:
ha ha I got accepted and ranked 2 in this problem with timing 0:00.230

albet_januar
New poster
Posts: 35
Joined: Wed Apr 12, 2006 6:03 pm
Location: jakarta, indonesia
Contact:
i got TLE for this problem..
i really confuse bout the O( n^3 ), can anybody help me??

Code: Select all

``````Deleted
``````
Last edited by albet_januar on Sun Apr 22, 2007 7:07 pm, edited 1 time in total.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
Your complexity is O(n^4). It can be solved in O(n^3).
Ami ekhono shopno dekhi...
HomePage

albet_januar
New poster
Posts: 35
Joined: Wed Apr 12, 2006 6:03 pm
Location: jakarta, indonesia
Contact:
any idea for doing O( n^3 )??

i don't have idea..

shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA
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
New poster
Posts: 35
Joined: Wed Apr 12, 2006 6:03 pm
Location: jakarta, indonesia
Contact:
i had solve prob 108.. i use o(n^4)
i cannot think bout the o(n^3) algorithms..

forthright48
New poster
Posts: 37
Joined: Wed Mar 14, 2012 11:57 am
Contact:

### Re:

shamim wrote: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?
What ever happens, happens for good. Even when we get WA :p
http://www.forthright48.com

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 10827 - Maximum sum on a torus

Duplicate the original N by N matrix to a 2 * N by 2 * N matrix and then run Kadane’s algorithm.
Check input and AC output for thousands of problems on uDebug!