Page 14 of 16
Posted: Mon Jul 09, 2007 1:57 am
by 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!
Posted: Sun Sep 09, 2007 12:46 pm
by kwdikosno8
can someone explain me how can you find at LithiumDex's solution the complexity?
thnks in advance
Posted: Sun Sep 09, 2007 7:06 pm
by 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
WA in Prob 108
Posted: Tue Dec 25, 2007 4:44 pm
by 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?
your algorithm is right
Posted: Wed Jan 16, 2008 10:11 am
by 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.
108, am I on wrong way ?
Posted: Tue Feb 05, 2008 9:11 pm
by 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
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
Re: 108, am I on wrong way ?
Posted: Wed Feb 06, 2008 8:58 am
by 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.
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..
Posted: Wed Feb 06, 2008 10:43 am
by 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 :
The output with your correction is 1881017956. It was 9 before. It has to be 15 (with the sample output)
Posted: Wed Feb 06, 2008 7:56 pm
by 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);
Posted: Thu Feb 07, 2008 12:26 am
by Phob028
Yeah, it works for the sample input, thanks !
I've found an other small mistake in my conditions :
but always got WA and I don't find an input that don't work :s
Posted: Thu Feb 07, 2008 6:03 am
by emotional blind
I have done a mistake, Sorry for that
Replace
by
Posted: Thu Feb 07, 2008 8:24 am
by Phob028
Accepted
I thank you a lot, and you have teached me something (I didnt knew this notation (m&&n)?1:2;)
Posted: Thu Feb 07, 2008 8:29 am
by emotional blind
Good Practice: Remove code after getting accepted.
Re: 108, am I on wrong way ?
Posted: Sun May 04, 2008 12:43 pm
by 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??
Re: 108, am I on wrong way ?
Posted: Tue May 27, 2008 5:45 pm
by 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.