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

smilitude
Experienced poster
Posts: 137
Joined: Fri Jul 01, 2005 12:21 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
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
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

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

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 ?

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.

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 ?

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

Phob028
New poster
Posts: 4
Joined: Tue Feb 05, 2008 9:03 pm
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.

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

emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:
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
Accepted
I thank you a lot, and you have teached me something (I didnt knew this notation (m&&n)?1:2;)

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

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 ?

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.