OJ Board

Posted: **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.

Posted: **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?

Posted: **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?

Posted: **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.

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

Posted: **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?

Posted: **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):)

Posted: **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

Posted: **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.

Posted: **Wed Jan 28, 2004 6:42 am**

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

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

Posted: **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!

If you get a program as fast as 0.000 seconds your memory usage will be 64K!

Ciao!!!

Claudio

Posted: **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.

Posted: **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

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

Posted: **Wed Jan 28, 2004 5:17 pm**

POST REMOVED

Posted: **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

Bye
Riyad

Posted: **Thu Jan 29, 2004 6:49 am**

Thanks for CDiMa's reply.
Now I know much about the OJ.

OJ Board

623 - 500!

possible improvements

Analytic Discussion

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

Sorry for being stupid :(