10007 - Count the Trees

[Julien Cornebise]

Hi
Is there a simple way of storing *VERY* big integers in C (around 10^50) ? Is <openssl/bn.h> allowed ? Or do we have to implement our own system ?
Thks

Julien

[cyfra]

Hi!

I don't think it is possible
I have implemented my own procedures for multiplication and addition ...

It really helpful and you need to do this once..


Good Luck

[Subeen]

<openssl/bn.h> is not allowed.
simply use string and make ur own function
to reduce space and time u can mask the numbers to int or long int. suppose u r using an char type array to store a 18 digit number. so u need 18 bytes mem. but u can use 2 long int that takes 8 bytes mem to store the number.
hope u will develop the procedure to deal with big numbers!

[Julien Cornebise]

Okay thank you very much all of you
That's what I've done, and it works great : base 10000 on short ints. Wonderful, and the first thinkg to bring on paper on the ACM contest...

Good bye, thanks again, and may ACM be with you

[Stefan Pochmann]

Don't you have Java in your contests? For me, it would be the last thing to bring with me if Java is supported... On the other hand, Java is for me the last thing to use unless I need to deal with big numbers. Well, garbage collection is kind of nice, I admit that...

[soyoja]

Java provide so simple solution. If you can use Java.Math.Biginteger

method, you'll handle biginteger easy.

Please check Java library reference. : )

[Fresh]

Hi,

Does anyone know how to create a base 100000000 class? Am I need to use int array where every index hold 0 - 99999999 ('%' by 1000000000)? Is it very slow?

-novice

[Adrian Kuegel]

I have used int array (also base 100000000) for solving P10247 and P10254. I think it is quite fast for addition (cf. P10254), but I had to convert one number to base 10 if I wanted to multiply them, which makes it much slower.

[10153EN]

You can convert the number to base 10000, which is capable of addition and multiplication without exceeding the boundary of int.

I have used this method to solve the problems which need the calculation of big numbers.

[Rossi]

What's the problem with this one ??? i'm getting lots of segsegv....

#include<stdio.h>

#define NUM 33
#define MAX 15

long int facs[NUM][MAX];
long int cats[NUM][MAX];
long int finl[NUM][MAX];

void buildfacs();
void buildcats();
void buildfinl();

int main(void)
{
register int i;
int index;

buildfacs();
buildcats();
buildfinl();

while(1){
scanf("%d",&index);
if(index==0)
break;

for(i=MAX-1;i>=0;i--){
if(finl[index]!=0)
break;
}
printf("%ld",finl[index]);
for(--i;i>=0;i--)
printf("%04ld",finl[index]);
printf("\n");
}
return 0;
}

void buildfacs()
{
register int i,j;

for(i=0;i<NUM;i++){
for(j=0;j<MAX;j++)
facs[j]=0;
}

facs[0][0]=1;
for(i=1;i<NUM;i++){
for(j=0;j<MAX;j++){
facs[j]+=(facs[i-1][j]*i);
if(facs[j]>=10000){
facs[j+1]+=facs[j]/10000;
facs[j]%=10000;
}
}
}
}

void buildcats()
{
register int i,j,k,l;

for(i=0;i<NUM;i++){
for(j=0;j<MAX;j++)
cats[j]=0;
}

cats[0][0]=1;
for(i=1;i<NUM;i++){
for(l=0;l<i;l++){
for(j=0;j<MAX;j++){
for(k=0;k<MAX;k++){
cats[i][j+k]+=(cats[l][j]*cats[i-1-l][k]);
if(cats[i][j+k]>=10000){
cats[i][j+k+1]+=cats[i][j+k]/10000;
cats[i][j+k]%=10000;
}
}
}
}
}
}

void buildfinl()
{
register int i,j,k;

for(i=0;i<NUM;i++){
for(j=0;j<MAX;j++)
finl[i][j]=0;
}

for(i=1;i<NUM;i++){
for(j=0;j<MAX;j++){
for(k=0;k<MAX;k++){
finl[i][j+k]+=(facs[i][j]*cats[i][k]);
if(finl[i][j+k]>=10000){
finl[i][j+k+1]+=finl[i][j+k]/10000;
finl[i][j+k]%=10000;
}
}
}
}
}

[/c]

[hujialie]

I originally solved this problem by using
following recursive formula:

f(0)=0;
f(1)=1;
f(n)=sigma(f(i)*f(n-i)) 0<=i<n
and ans(n)=f(n)*n!

but after the limit of n had been changed, this method
is too slow and troublesome to code, could anyone
recommend a better one?

[Larry]

I used the formula 2n!/(n-1)! and coded it in Java and got it AC. Maybe you should cache the value.

[..]

Could you tell me how you got this simple formula??

[Larry]

I did this problem a long time ago, and all I did was changed the array size, so correct me if I'm not too clear:

It is clear that Catalan numbers are used, with binary trees and all, and the lesser known way of writing Catalan numbers is:

2n! / (n! * (n+1)! )

If you don't understand above, look up on mathworld or google.

Then you realize there's n! way of labeling each of the tree, so you just multiply it by n!. I think the indices might be off by 1 in this explanation, and I think I just fudged it by fixing it until it matches the output.. but this was my general thought process.

[Larry]

(To think of it, hujialie did the same thing, but basically, I wrote out the explicit form instead..)