10007 - Count the Trees

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

Moderator: Board moderators

Julien Cornebise
Experienced poster
Posts: 145
Joined: Sat Feb 23, 2002 2:00 am
Location: Paris, France
Contact:

10007 - Count the Trees

Post by Julien Cornebise » Sat Feb 23, 2002 11:24 pm

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
Experienced poster
Posts: 144
Joined: Thu Nov 22, 2001 2:00 am
Location: Gdynia, Poland

Post by cyfra » Fri Mar 15, 2002 6:01 pm

Hi!

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

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


Good Luck :smile:

Subeen
Experienced poster
Posts: 127
Joined: Tue Nov 06, 2001 2:00 am
Location: Bangladesh
Contact:

Post by Subeen » Fri Mar 22, 2002 6:40 am

<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
Experienced poster
Posts: 145
Joined: Sat Feb 23, 2002 2:00 am
Location: Paris, France
Contact:

Post by Julien Cornebise » Fri Mar 22, 2002 7:43 pm

Okay thank you very much all of you :smile:
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 :grin:

Stefan Pochmann
A great helper
Posts: 284
Joined: Thu Feb 28, 2002 2:00 am
Location: Germany
Contact:

Post by Stefan Pochmann » Sat Mar 23, 2002 3:02 am

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
Experienced poster
Posts: 106
Joined: Sun Feb 17, 2002 2:00 am
Location: Seoul, South Korea
Contact:

Use Java.Math.Biginteger

Post by soyoja » Tue May 07, 2002 5:53 pm

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

method, you'll handle biginteger easy.

Please check Java library reference. : )

Fresh
New poster
Posts: 46
Joined: Mon Apr 15, 2002 10:42 am
Contact:

Base 100000000

Post by Fresh » Wed May 08, 2002 4:57 am

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
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Wed May 08, 2002 9:54 am

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
Experienced poster
Posts: 148
Joined: Sun Jan 06, 2002 2:00 am
Location: Hong Kong
Contact:

Hi~~

Post by 10153EN » Wed May 08, 2002 12:20 pm

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
New poster
Posts: 20
Joined: Thu Mar 21, 2002 2:00 am
Location: Bangladesh

Post by Rossi » Sat Jun 15, 2002 7:45 pm

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
New poster
Posts: 43
Joined: Thu Apr 17, 2003 10:24 am
Location: Shanghai,China

10007 WA after rejudged.

Post by hujialie » Sat Nov 22, 2003 4:32 pm

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?
Retired from SJTU Accelerator 2004

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Sat Nov 22, 2003 4:45 pm

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

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

Post by .. » Sat Nov 22, 2003 6:03 pm

Could you tell me how you got this simple formula?? :o
My signature:
  • Please make discussion about the algorithm BRFORE posting source code.
    We can learn much more in discussion than reading source code.
  • I HATE testing account.
  • Don't send me source code for debug.

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Sat Nov 22, 2003 6:16 pm

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
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Sat Nov 22, 2003 6:18 pm

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

Post Reply

Return to “Volume 100 (10000-10099)”