10303 - How Many Trees?

[Christian Schuster]

After the input limit was set to 1000, I got some time problems, and - with BigNum and DP - I currently reach about 21 seconds. I'm using a sum of products to find the number. My question:

Is there an explicit formula to calculate those numbers?

[Stefan Pochmann]

If I remember it correctly, this is covered on page 181 in the second edition of the CLRS book. Don't know about the first edition. Look up "catalan numbers" in the index, it's a "problem", I believe. The problem brings you step by step to a nice formula that I think makes it easy to step from C(n) to C(n+1), so you can precalc all fast.

Correction: it's on page 271 (I knew 181 looked wrong, but it had the correct checksum. I guess I'll have to update my brain with something less error-prone)

[Stefan Pochmann]

Yep, just solved it. Starting with the formula of CLRS, you can get an easy recurrence relation of the form

c[0] = 1
c[n+1] = f( n, c[n] )

where f is really a simple function.

Let's ignore that working with large numbers takes more time than with simple ints, i.e. let's assume the arithmetic operations for large numbers can be done in constant time. Then I can precompute the first n Catalan numbers in time O(n).

[yatsen]

Can you give me some hint how I can find out the "simple" function f?

I use c(n)=c(0)*c(n-1)+c(1)*c(n-2)+......+c(n-1)*c(0)
And I got time limit exceed.

[Stefan Pochmann]

I think you should really start with the formula mentioned in CLRS. Here it is:

c(n) = 1/(n+1) * (2n choose n)

Then rewrite the "choose" part with something more useful and try it like this:

c(n+1) = ... = and-here-something-that-includes-c(n)-and-not-much-more.

[yatsen]

I know the answer is c(n)=(4n-2/n+1) c(n-1) by your hint.
Thank you very much!
But my question is how the fomula c(n) = 1/(n+1) * (2n choose n) comes from?
I am sorry I don't know anything about CLRS. Is there any reference I can find out for the formula in the internet?

[rjhadley]

CLRS is the book "Introduction to Algorithms" by Cormen, Leiserson, Rivest, and Stein. (ISBN 0262032937)

[LittleJohn]

But my question is how the fomula c(n) = 1/(n+1) * (2n choose n) comes from?
I am sorry I don't know anything about CLRS. Is there any reference I can find out for the formula in the internet?

There's a good web site about math: http://mathworld.wolfram.com/
You may go and search for "Catalan Number."

[hs]

Can anyone post the result for 1000?
I keep getting wrong answer!!!

[Junayeed]

i think this is the correct output for 1000:

2046105521468021692642519982997827217179245642339057975844538099572176010191891863964968026156453752449015750569428595097318163634370154637380666882886375203359653243390929717431080443509007504772912973142253209352126946839844796747697638537600100637918819326569730982083021538057087711176285777909275869648636874856805956580057673173655666887003493944650164153396910927037406301799052584663611016897272893305532116292143271037140718751625839812072682464343153792956281748582435751481498598087586998603921577523657477775758899987954012641033870640665444651660246024318184109046864244732001962029120

[hs]

Thanks, i finally solved it.

[ithamar]

Pleas can you kindly edit the message that shows the answer to 1000.

It makes the board wideeeeeeeeeeeeeeeer and it doesnt look right.

[medv]

Help me please to solve 10303. I use formula
f(n) = 1/(n+1) * (2n choose n) = (n+2)*(n+3)*...*(2n) / (1*2*...*n).
All my tests seems right. Why WA?
I tried to change readln to read, integer to longint - but it didn't help me.
Help me if you can.

My code is here:

program How_Many_Trees_10303;
const
max = 1000;
Len = 1000;
var
i,j,z,t,n:longint;
m:array[1..max] of longint;
res:array[1..Len] of longint;
pres:longint;

function nsd(a:longint;b:longint):longint;
begin
if (a = 0) then nsd := b else
if (b = 0) then nsd := a else
if (a >= b) then nsd := nsd(a mod b, b) else
nsd := nsd(a, b mod a);
end;

procedure mult(nn:longint);
var
i,t:longint;
temp:array[1..Len] of longint;
begin
t := 0;
for i:=1 to pres do
begin
t := res[i]*nn + t;
temp[i] := t mod 10;
t := t div 10;
end;
while (t > 0) do
begin
Inc(pres);
temp[pres] := t mod 10;
t := t div 10;
end;
for i:=1 to pres do res[i] := temp[i];
end;

begin
read(n);
while True do
begin
for i:=2 to n do m[i] := n+i;
for i:=2 to n do
begin
z := i;
for j:=2 to n do
begin
t := nsd(z,m[j]);
z := z div t;
m[j] := m[j] div t;
if (z = 1) then break;
end;
end;
for i:=1 to Len do res[i] := 0; res[1] := 1; pres:=1;
for i:=2 to n do
if m[i] > 1 then
mult(m[i]);
for i:=pres downto 1 do write(res[i]);
read(n);
if (n > 0) then writeln else break;
end;
end.

[..]

This is the output for 1000, are you correct on it?
2046105521468021692642519982997827217179245642339057975844538099572176010191891863964968026156453752449015750569428595097318163634370154637380666882886375203359653243390929717431080443509007504772912973142253209352126946839844796747697638537600100637918819326569730982083021538057087711176285777909275869648636874856805956580057673173655666887003493944650164153396910927037406301799052584663611016897272893305532116292143271037140718751625839812072682464343153792956281748582435751481498598087586998603921577523657477775758899987954012641033870640665444651660246024318184109046864244732001962029120

[medv]

Thank you. Yes, my program gives correct solution when n=1000.
I tried to rewrite it in C, but also gets WA.

If you have accepted this problem, please - send me your solution.