10827  Maximum sum on a torus
Moderator: Board moderators
 emotional blind
 A great helper
 Posts: 383
 Joined: Mon Oct 18, 2004 8:25 am
 Location: Bangladesh
 Contact:

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

 New poster
 Posts: 35
 Joined: Wed Apr 12, 2006 6:03 pm
 Location: jakarta, indonesia
 Contact:
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.
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.

 New poster
 Posts: 35
 Joined: Wed Apr 12, 2006 6:03 pm
 Location: jakarta, indonesia
 Contact:

 New poster
 Posts: 37
 Joined: Wed Mar 14, 2012 11:57 am
 Location: Bangladesh
 Contact:
Re:
I tried by eliminating the smallest rectangle to get the wrap value. But then I realized, this method cannot handle case like: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.
Code: Select all
1
3
100 100 100
100 100 100
100 100 100
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?

 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!