108 - Maximum Sum

[smilitude]

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!

[kwdikosno8]

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

thnks in advance

[tgoulart]

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

[kalachan]

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]

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]

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

[emotional blind]

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.

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

[Phob028]

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)

[emotional blind]

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]

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

[emotional blind]

I have done a mistake, Sorry for that
Replace

Code: Select all

m&n

by

Code: Select all

m&&n

[Phob028]

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

[emotional blind]

Good Practice: Remove code after getting accepted.

[carot]

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]

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.