Page 2 of 13

:)

Posted: Sun Jan 18, 2004 12:48 pm
by pavelph
It's very funny: the name of problem is 500!, but you must to solve 1000! :) I had got 3 WA before find that input can has nubers>500. :roll:

Posted: Sun Jan 18, 2004 4:21 pm
by Zhao Le
Didn't you notice that the upper limit of n has been increased to 1000 ?
I really don't notice that.
Because I have already downloaded the Problem and not go online to see what has been changed.
Next time I should be more careful.

But now it got TLE.
I just changed the Max from 1135 to 3000.
and better way to avoid TLE?

The code is deleted because I think it is no need to post it.
Not the code itself problem.

Posted: Sun Jan 18, 2004 11:50 pm
by Ivan Golubev
Test your code with input:
1
2
3
...
999
1000

And you'll figure out why it gots TLE.
[Something like a hint] While you're computing 1000! you're computing all other factorial values as well... what's the reason to do same calculations several times?..

Posted: Mon Jan 19, 2004 4:21 am
by Zhao Le
The only way I know DP is to use a matrxi like BigInteger[500][3000]
but I can just compile not run in my VC++6.0 compiler.

And I wondered whether that such big a maxtrix will cause Memory Overflow.

Posted: Mon Jan 19, 2004 6:56 am
by horape
Zhao Le wrote:The only way I know DP is to use a matrxi like BigInteger[500][3000]
but I can just compile not run in my VC++6.0 compiler.

And I wondered whether that such big a maxtrix will cause Memory Overflow.
500 * 3000 * sizeof(int) = 6000000 (6M), not so big.

you're probably exceeding the stack size, try defining it as a global variable.

Saludos,
HoraPe

Posted: Mon Jan 19, 2004 12:08 pm
by CDiMa
Zhao Le wrote:The only way I know DP is to use a matrxi like BigInteger[500][3000]
Maybe BigInteger[1000][3000] is more appropriate for problem 623 ;)

Ciao!!!

Claudio

Posted: Mon Jan 19, 2004 12:32 pm
by anupam
As far as i know, many contestent faces problems compiling and running with an array of [1000][2600].

It is memory limit exceeded.
Even sometimes it doesn't take the input and if you are compile with VC++ 6.00, it will show an error msg and exit.

It you use cygwin you will again get memory dump error.

If you try to generate all instantly you will get tle.
If you try to generate only those neede for input(memoiztion) you will again get tle as i think they had given all the test cases from 1-1000..or something like that.

So, many methods to solve the problem will get problem.
--
Anupam

Posted: Mon Jan 19, 2004 2:50 pm
by Zhao Le
So, many methods to solve the problem will get problem.
I don't really know much about DP except using Matrix.

can you how me an example?

HEY WA IN THIS

Posted: Fri Jan 23, 2004 11:07 am
by Riyad
hey some one help me plizzzzzzz . i am getting wa at this after rejudgement . is there any tricky input . i hate to paste code but i am really very confused with this prob. i know that the prob statement has changed and it is changed to 1000 instead of 500. here is part of my code .


[cpp]BINT result[1002];

void precalculate(){

int i , j ;
BINT one , x , y ;

one.setInt("1");
x.setInt("1");
y.setInt("1");


for(i=1,j=1;i<=1001;i++){
y=y*x;
result[j++]=y;
x=x+one;

}

}



int main(){

int check;
precalculate();

while(scanf("%d",&check)==1){

if(check==0){

cout<<check<<"!"<<endl;
cout<<"0"<<endl;
continue;
}

cout<<check<<"!"<<endl;
cout<<result[check]<<endl;
}

return 0;

}[/cpp]

plizzzzzzzzzzzzzzzzzzz help me in this .
Bye
Riyad

Re: HEY WA IN THIS

Posted: Fri Jan 23, 2004 12:25 pm
by CDiMa
Riyad wrote:hey some one help me plizzzzzzz . i am getting wa at this after rejudgement . is there any tricky input . i hate to paste code but i am really very confused with this prob. i know that the prob statement has changed and it is changed to 1000 instead of 500. here is part of my code .


[cpp]BINT result[1002];[/cpp]
This problem hasn't any tricky input. Make sure it outputs correct answers for any integer from 0 upto 1000. Make also sure that BINT handles the result for 1000 which has more that 2500 digits...

Ciao!!!

Claudio

Posted: Sat Jan 24, 2004 6:36 am
by junjieliang
Zhao Le:
I don't really know much about DP except using Matrix
How do you use matrix to find factorials?

Btw for this problem would there be TLE/MLE if we just precalculate all factorials and store the numbers in arrays? I haven't tried this yet but if the memory used is not too great it sounds like a good solution...

Posted: Sun Jan 25, 2004 8:06 pm
by anupam
yes, I think so. It's not a good solution taking all the values precalculated.[/i]

Posted: Mon Jan 26, 2004 8:52 am
by Zhao Le
I used precalucation while using Matrix to store but only to find TLE.
I did not make any more progress these days.

Posted: Mon Jan 26, 2004 9:12 am
by anupam
Zhao Le wrote:I used precalucation while using Matrix to store but only to find TLE..
I know you will get as I hope here are all he cases possible and even more than one ocurence for the same case.:-))

Posted: Mon Jan 26, 2004 11:09 am
by Adrian Kuegel
Precalculation works fine. Of course you shouldn't calculate each n! alone, you should compute n! as n*(n-1)! (the value (n-1)! is already stored in your precomputation table).