623 - 500!

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

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

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

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

[horape]

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

[CDiMa]

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

[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

[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?

[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

[CDiMa]

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

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

[anupam]

yes, I think so. It's not a good solution taking all the values precalculated.[/i]

[Zhao Le]

I used precalucation while using Matrix to store but only to find TLE.
I did not make any more progress these days.

[anupam]

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

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