108 - Maximum Sum

All about problems in Volume 1. 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
smilitude
Experienced poster
Posts: 137
Joined: Fri Jul 01, 2005 12:21 am

Post by smilitude » Mon Jul 09, 2007 1:57 am

phew!
if anyone gets stuck with 108, plz note that this type of problems are very usual.. i was surprised to see how many 'almost same' are there!
and you can read the ioi 05 task garden's solution - just to get a good and easy understanding! seriously! i am not joking! (though 108 is a subproblem of garden)

http://www.ioi2005.pl/olympiad/ is the address!
fahim
#include <smile.h>

kwdikosno8
New poster
Posts: 3
Joined: Sat Sep 08, 2007 2:38 am

Post by kwdikosno8 » Sun Sep 09, 2007 12:46 pm

can someone explain me how can you find at LithiumDex's solution the complexity?

thnks in advance

tgoulart
New poster
Posts: 42
Joined: Sat Oct 21, 2006 8:37 am
Location: Alegrete, Brazil

Post by tgoulart » Sun Sep 09, 2007 7:06 pm

In this situation, you just count the number of nested loops.

If you want to learn more, read this:

http://www.topcoder.com/tc?module=Stati ... omplexity1
Thiago Sonego Goulart - UFMG/Brazil

kalachan
New poster
Posts: 1
Joined: Mon Dec 24, 2007 2:23 pm

WA in Prob 108

Post by kalachan » Tue Dec 25, 2007 4:44 pm

Code: Select all

#include<iostream>
using namespace std;

int size;
int M[100][100];
long long partialSum[100][100];

int main()
{

	cin >> size;
	
	for (int i = 0; i < size; i ++)
		for (int j = 0; j < size; j ++)
			cin >> M[i][j];
	

	if (size <= 0)
	{
		cout << 0 << endl;
		return 0;
	}
	
	long long MaxSum = -4147483647;
	
	partialSum[0][0] = M[0][0];
	for (int i = 1; i < size; i++)
		partialSum[0][i] = partialSum[0][i - 1] + M[0][i]; 
	for (int i = 1; i < size; i++)
	{
		partialSum[i][0] = partialSum[i - 1][0] + M[i][0];
		for (int j = 1; j < size; j ++)
		{
			partialSum[i][j] = partialSum[i][j - 1] - partialSum[i - 1][j - 1] + partialSum[i - 1][j] + M[i][j];
		}
	}

	
	for (int i1 = 0; i1 < size; i1 ++)
		for (int i2 = i1; i2 < size; i2 ++)
			for (int j1 = 0; j1 < size; j1 ++)
				for (int j2 = j1; j2 < size; j2 ++)
				{
					long long sum = 0;
					if ((i1 == 0) && (j1 == 0)) sum = partialSum[i2][j2];
					else if (i1 == 0) sum = partialSum[i2][j2] - partialSum[i2][j1 - 1];
					else if (j1 == 0) sum = partialSum[i2][j2] - partialSum[i1 - 1][j2];
					else sum = partialSum[i2][j2] - partialSum[i1 - 1][j2] - partialSum[i2][j1 - 1] + partialSum[i1 - 1][j1 - 1];
					
					if (sum > MaxSum) MaxSum = sum; 
				}
				
	cout << MaxSum << endl;

	return 0;
}

I have test all the test case in the forum and i still can't find my error
could any body help?

caligue
New poster
Posts: 1
Joined: Wed Dec 26, 2007 8:07 am
Location: Japan
Contact:

your algorithm is right

Post by caligue » Wed Jan 16, 2008 10:11 am

your computation algorithm is right.
i think the problem is input. this is a multi input problem.
your program deals with only first case.
you have to input and compute till eof.

by the way, long long is not needed to compute sum;
int is enough in this problem.

Phob028
New poster
Posts: 4
Joined: Tue Feb 05, 2008 9:03 pm

108, am I on wrong way ?

Post by Phob028 » Tue Feb 05, 2008 9:11 pm

Hi,

I'm trying to solve the problem in C++
Tab is the input array, Tab2[j] is the sum from 0 to i and 0 to j in Tab

Code: Select all

done
I can't assure at all wether this line :

Code: Select all

tmp=Tab2[m][n]-Tab2[m][j-1]-Tab2[i-1][n]+Tab2[i-1][j-1];
is correct or not, maybe it has to be checked first :-?

PS : Here is only the part of my code where the error seems to be, I already have checked the useless parts
Last edited by Phob028 on Thu Feb 07, 2008 11:17 am, edited 1 time in total.

User avatar
emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:

Re: 108, am I on wrong way ?

Post by emotional blind » Wed Feb 06, 2008 8:58 am

May be this will be correct

Code: Select all

tmp=Tab2[i][j]-Tab2[m-1][j]-Tab2[i][n-1]+Tab2[m-1][n-1];
And from next time don't forget to post in existing related thread. If there is no thread exists related to your topic then you can create a new one. So search before post.
Phob028 wrote:PS : Here is only the part of my code where the error seems to be, I already have checked the useless parts
Are you sure those parts are useless? So why to check those rather then remove.. :wink:

Phob028
New poster
Posts: 4
Joined: Tue Feb 05, 2008 9:03 pm

Post by Phob028 » Wed Feb 06, 2008 10:43 am

Thanks for your answer, next time I will post in the related topic ;)

I think these parts are useless for finding the mistake(s), but that's my program :

Code: Select all

done
The output with your correction is 1881017956. It was 9 before. It has to be 15 (with the sample output)
Last edited by Phob028 on Thu Feb 07, 2008 11:16 am, edited 1 time in total.

User avatar
emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:

Post by emotional blind » Wed Feb 06, 2008 7:56 pm

What about this line:

Code: Select all

tmp=Tab2[i][j]-(m?Tab2[m-1][j]:0)-(n?Tab2[i][n-1]:0)+((m&n)?Tab2[m-1][n-1]:0);

Phob028
New poster
Posts: 4
Joined: Tue Feb 05, 2008 9:03 pm

Post by Phob028 » Thu Feb 07, 2008 12:26 am

Yeah, it works for the sample input, thanks !
I've found an other small mistake in my conditions :

Code: Select all

done
but always got WA and I don't find an input that don't work :s
Last edited by Phob028 on Thu Feb 07, 2008 11:15 am, edited 1 time in total.

User avatar
emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:

Post by emotional blind » Thu Feb 07, 2008 6:03 am

I have done a mistake, Sorry for that
Replace

Code: Select all

m&n
by

Code: Select all

m&&n

Phob028
New poster
Posts: 4
Joined: Tue Feb 05, 2008 9:03 pm

Post by Phob028 » Thu Feb 07, 2008 8:24 am

Accepted :D
I thank you a lot, and you have teached me something (I didnt knew this notation (m&&n)?1:2;)

User avatar
emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:

Post by emotional blind » Thu Feb 07, 2008 8:29 am

Good Practice: Remove code after getting accepted.

carot
New poster
Posts: 1
Joined: Sun May 04, 2008 12:39 pm

Re: 108, am I on wrong way ?

Post by carot » Sun May 04, 2008 12:43 pm

i get a Time limit exceeded in problem 108, but
the max depth of loop of my program is only 2....
and i use c++...

who can tell me why??

RC's
Learning poster
Posts: 65
Joined: Fri Jul 13, 2007 3:17 pm

Re: 108, am I on wrong way ?

Post by RC's » Tue May 27, 2008 5:45 pm

what do you mean by saying your max depth loop is only 2 ?
Do you mean your program runs in O(n^2) ? It's amazing.
I think O(n^3) and O(n^4) will get AC, and I don't know how to figure an O(n^2) solution..
Maybe you can paste your code here to make it clear.

Post Reply

Return to “Volume 1 (100-199)”