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

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

Post by Zhao Le » Tue Jan 27, 2004 9:07 am

Adrian Kuegel wrote: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).
I think it surely will get MLE(Memory Limit Execeeded).
as I memtioned above.
anupam wrote:I know you will get as I hope here are all he cases possible and even more than one ocurence for the same case.
but how should I handle without Matrix?

I mean when first time 1000 appears I calcaulated but second time it appears what I should do?
use Matrix to store?(It will cause Memory Limit Excessed I think)


give me some hint or other.

Thanks.
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 » Tue Jan 27, 2004 11:02 am

It won't get TLE, forget about anupam's posts -- he's wrong (btw, never trust posts written in bold (and italic) fonts).
Even if you'll declare array as char facts[1001][2600] it will only takes 2.5M of memory. Is this too much? Don't think so.
About computation, it's trivial:

Code: Select all

BigInteger facts[1001];
void gen(void)
{
 int i;

 facts[0] = 1;
 for (i=1; i<=1000; i++) facts[i] = i * facts[i - 1];
}
Can be anything easier than this?

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

Post by anupam » Tue Jan 27, 2004 12:23 pm

Ivan Golubev wrote:It won't get TLE, forget about anupam's posts -- well you may
he's wrong --ofcourse i may
(btw, never trust posts written in bold (and italic) fonts).:-) then why they are given?. please request he admins to remove them:-)



Even if you'll declare array as char facts[1001][2600] it will only takes 2.5M of memory. Is this too much? Don't think so.
About computation, it's trivial:

Code: Select all

BigInteger facts[1001];
void gen(void)
{
 int i;

 facts[0] = 1;
 for (i=1; i<=1000; i++) facts[i] = i * facts[i - 1];
}
Can be anything easier than this?
"Everything should be made simple, but not always simpler"

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

Post by anupam » Tue Jan 27, 2004 12:48 pm

Hello,

The board is not for personal atack. You can never find me attacking on ohers. The board is for discussions. If you dislike one, don't express it here, rather You may easily PM him/her. None but a fool is always right. :wink:

And about bold italic. I use the style. Many oher can use the style. Why do you assume that all of them are bogus??

You can't think everybody like you. and I am wrong, I found. as I got accepted it just now with two solutions.

Precalculation is ok here. But I have three solution with MLE with precalculation.

Keep cool. Programming is fun here, please don't think it anything else.

--
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 » Tue Jan 27, 2004 4:16 pm

So who should I trust?

Maybe I just trust myself?

Thanks for anupam & Ivan Golubev and also others who replys to me.

I think the one came here have high educated not just juys around the street.
So calm down ok?
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 » Tue Jan 27, 2004 5:26 pm

Hello,
You can trust (depending your thought) these words..
"You can get accepted by generating all the answers.
First make a array of [1001][2600];
then assign a[0][0]=1;
then use the method
for(i=1;i<1001;i++) a=a[i-1]*i; or
for(i=1;i<1001;i++) a=milt(a,i);
depending on whether you use c or c++.

Your multiplication function should be very fast.
Don't try to multiply all the array elements (In that case you will get TLE). Try to multiply only to the length of a[i-1] to achive the value of a.
You can use a endmarker like -1
for xample,

a[0]={1,-1,...all not used}
a[1]={1,-1,...all not used};
a[5]={1,2,0,-1,...all not used};

sometimes you may get MLE if you use more element arrays,

sometimes your program may not take input ( i don't know why )
Thanks to Golubev and Adrian for there advices to me.
Don't think. I have learnt a lot from this board. I had joined here when I was an amature.
--
Anupam (never wants to create enemies, wants friendship):)
"Everything should be made simple, but not always simpler"

User avatar
abishek
Experienced poster
Posts: 131
Joined: Mon Dec 15, 2003 5:41 am

possible improvements

Post by abishek » Tue Jan 27, 2004 6:48 pm

hi
there is no problem in precomputation and storing in a matrix as my AC does that.
Certainly the algorithm should calculate n! as n * (n - 1)! and finish it off in O(n) large multiplications.
Also the new testcase I believe contains 0! and that is why people are getting TLE.
Hope it helped
bye

User avatar
shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

Analytic Discussion

Post by shamim » Wed Jan 28, 2004 6:12 am

Let us discuss the matter analytically:

if you run the following program, you will see that the number of digits of
1000! is app. 2570.

[cpp]#include<math.h>
#include<stdio.h>
int main()
{
double num=0;
long val;

for ( val=1; val<=1000; val++)
num = num + log10(val);


printf("%.0lf", num+1);
return 0;
}[/cpp]

Therefore this is the worst case on the size of the required factorial.

Therefore we will need a character array line this:

char facts[1001][2570];

whose size is 1001*2570 = 2572570 or app. 2.57 MB, much less than the stipulated 32 MB. So there is no question about memory limit.

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

Post by Zhao Le » Wed Jan 28, 2004 6:42 am

Thanks all guy who replied to me.
I got AC now.
:P :P :P

But one more thing how should I reduce the Memory Usage?
My Memory use is 10488

And time running is 0:00.668

how can I reduce the memory?

Thanks
AC makes me feels good,
But WA makes me thinks hard.

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

Post by CDiMa » Wed Jan 28, 2004 2:55 pm

Zhao Le wrote:But one more thing how should I reduce the Memory Usage?
My Memory use is 10488

And time running is 0:00.668

how can I reduce the memory?

Thanks
Speedup your program! 8)
If you get a program as fast as 0.000 seconds your memory usage will be 64K! :P

Ciao!!!

Claudio

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

Post by Zhao Le » Wed Jan 28, 2004 3:24 pm

I think memory usage is depending on how much Matrix you used,
Not depending how fast the program running.

I use S[1000][2570] so the memory is large and I wanna figure out why others in the top list could use so little memory.

Maybe they use better algorithm,like DP I don't know.
AC makes me feels good,
But WA makes me thinks hard.

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

Post by CDiMa » Wed Jan 28, 2004 4:42 pm

Zhao Le wrote:I think memory usage is depending on how much Matrix you used,
Not depending how fast the program running.
I was just kidding about a bug/feature of the online-judge.
Of course the speed of your program doesn't affect the effective amount of memory used, but low times in the online-judge reduce the memory usage reported.
You'll surely have noted in stats that 0,000 times corresponds to 64K memory usage...
In my prog I use a 2meg structure to hold the calculated data but the stats tell 64K 8)
Zhao Le wrote:I use S[1000][2570] so the memory is large and I wanna figure out why others in the top list could use so little memory.

Maybe they use better algorithm,like DP I don't know.
Actually DP uses mem to store pevious calculations, so it should increase mem usage...

Anyway you aren't forced to store digits one by one. It depends on the size of the base you choose to store your bignums.
One could use 2^32, 10^9, 2^16, 10 or any useful value.
For general purpose bignums I use 10^4, for this problem I used 10^6 since 10^6*1000 fits in an int...

Ciao!!!

Claudio

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

!!!!!!!!!!!!!!!!!!!!!!!!!!

Post by Riyad » Wed Jan 28, 2004 5:17 pm

POST REMOVED
Last edited by Riyad on Wed Jan 28, 2004 5:39 pm, edited 1 time in total.
HOLD ME NOW ,, I AM 6 FEET FROM THE EDGE AND I AM THINKIN.. MAY BE SIX FEET IS SO FAR DOWN

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

Sorry for being stupid :(

Post by Riyad » Wed Jan 28, 2004 5:34 pm

hey i got it AC . i did not counter the inputs well . i was missing the output for 0 which i got it right 8)
Bye
Riyad
HOLD ME NOW ,, I AM 6 FEET FROM THE EDGE AND I AM THINKIN.. MAY BE SIX FEET IS SO FAR DOWN

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

Post by Zhao Le » Thu Jan 29, 2004 6:49 am

Thanks for CDiMa's reply.
Now I know much about the OJ.
AC makes me feels good,
But WA makes me thinks hard.

Post Reply

Return to “Volume 6 (600-699)”