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
emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:

Post by emotional blind » Tue Apr 25, 2006 7:40 pm

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:

Post by albet_januar » Wed Apr 18, 2007 6:29 pm

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
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Wed Apr 18, 2007 7:15 pm

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:

Post by albet_januar » Sun Apr 22, 2007 7:15 pm

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

i don't have idea..

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

Post by shamim » Mon Apr 23, 2007 1:38 pm

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:

Post by albet_januar » Wed Jun 06, 2007 6:25 pm

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
Location: Bangladesh
Contact:

Re:

Post by forthright48 » Sun Aug 18, 2013 6:24 pm

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

Post by brianfry713 » Mon Aug 19, 2013 10:18 pm

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!

Post Reply

Return to “Volume 108 (10800-10899)”