623 - 500!

All about problems in Volume 6. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

pavelph
Learning poster
Posts: 57
Joined: Wed Dec 10, 2003 7:32 pm
Location: Russia, Saint-Petersburg

:)

Post by pavelph » Sun Jan 18, 2004 12:48 pm

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:

Zhao Le
Learning poster
Posts: 80
Joined: Mon May 05, 2003 4:09 am
Location: Shanghai,China

Post by Zhao Le » Sun Jan 18, 2004 4:21 pm

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.
Last edited by Zhao Le on Tue Jan 27, 2004 9:10 am, edited 1 time in total.
AC makes me feels good,
But WA makes me thinks hard.

Ivan Golubev
Experienced poster
Posts: 167
Joined: Fri Oct 19, 2001 2:00 am
Location: Saint Petersburg, Russia

Post by Ivan Golubev » Sun Jan 18, 2004 11:50 pm

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
Learning poster
Posts: 80
Joined: Mon May 05, 2003 4:09 am
Location: Shanghai,China

Post by Zhao Le » Mon Jan 19, 2004 4:21 am

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.
AC makes me feels good,
But WA makes me thinks hard.

User avatar
horape
New poster
Posts: 49
Joined: Sat Sep 13, 2003 3:18 pm
Location: Buenos Aires

Post by horape » Mon Jan 19, 2004 6:56 am

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

CDiMa
Experienced poster
Posts: 214
Joined: Fri Oct 17, 2003 5:49 pm
Location: Genova

Post by CDiMa » Mon Jan 19, 2004 12:08 pm

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

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:

Post by anupam » Mon Jan 19, 2004 12:32 pm

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
"Everything should be made simple, but not always simpler"

Zhao Le
Learning poster
Posts: 80
Joined: Mon May 05, 2003 4:09 am
Location: Shanghai,China

Post by Zhao Le » Mon Jan 19, 2004 2:50 pm

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?
AC makes me feels good,
But WA makes me thinks hard.

User avatar
Riyad
Experienced poster
Posts: 131
Joined: Thu Aug 14, 2003 10:23 pm
Location: BUET
Contact:

HEY WA IN THIS

Post by Riyad » Fri Jan 23, 2004 11:07 am

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
HOLD ME NOW ,, I AM 6 FEET FROM THE EDGE AND I AM THINKIN.. MAY BE SIX FEET IS SO FAR DOWN

CDiMa
Experienced poster
Posts: 214
Joined: Fri Oct 17, 2003 5:49 pm
Location: Genova

Re: HEY WA IN THIS

Post by CDiMa » Fri Jan 23, 2004 12:25 pm

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

junjieliang
Experienced poster
Posts: 169
Joined: Wed Oct 31, 2001 2:00 am
Location: Singapore

Post by junjieliang » Sat Jan 24, 2004 6:36 am

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
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:

Post by anupam » Sun Jan 25, 2004 8:06 pm

yes, I think so. It's not a good solution taking all the values precalculated.[/i]
"Everything should be made simple, but not always simpler"

Zhao Le
Learning poster
Posts: 80
Joined: Mon May 05, 2003 4:09 am
Location: Shanghai,China

Post by Zhao Le » Mon Jan 26, 2004 8:52 am

I used precalucation while using Matrix to store but only to find TLE.
I did not make any more progress these days.
AC makes me feels good,
But WA makes me thinks hard.

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:

Post by anupam » Mon Jan 26, 2004 9:12 am

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.:-))
"Everything should be made simple, but not always simpler"

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Mon Jan 26, 2004 11:09 am

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

Post Reply

Return to “Volume 6 (600-699)”