## 10643 - Facing Problem With Trees

Moderator: Board moderators

football2001
New poster
Posts: 2
Joined: Wed May 05, 2004 8:52 am

### 10643 - Facing Problem With Trees

Can anyone tell me how to solve this problem?Thanks.
Does it have a formula?

Maniac
Experienced poster
Posts: 105
Joined: Tue Oct 14, 2003 3:24 pm
Location: Utrecht, Holland

### 10643 - faster DP solution?

Hi all,

I solved problem 10643 'Facing Problem with trees' but I sent in precalced table of values. This precalculation took about 1 min on my machine and just sending in my solution gave a TLE (that's why I saw myself forced to precalculate). However, I see people with solutions to this problem taking only 1 sec so I was wondering wether my approach could be improved.

In my approach, I keep two arrays:

nsimple[m] - the number of binary trees with m edges
ncomplicated[m][n] - the number of trees with m edges and n outgoing edges from root

the desired answer for m edges would then be

answer[m] = sum{n=0; n<=m; n+=2} ncomplicated[m][n]

I calculated these arrays using the following recursion relations:

nsimple[0] = 1
nsimple[m] = sum{i=0; i<=m-2; i+=2} nsimple*nsimple[m-2-i]

ncomplicated[0][0] = 1
ncomplicated[m][2] = nsimple[m]
ncomplicated[m][n] = sum{i=n-2; i<=m-2; i+=2} ncomplicated[n-2]*nsimple[m-i]

Filling the ncomplicated array requires about 2 million additions and multiplications (it's of order m^3). But each multiplication requires about 20*20 = 400 operations worst case, because the numbers can grow up to 200 digits (I use a BigInt implementation with an array of longs, base 10^9, so about 20 longs are required for a 200 decimaldigit-number). So all in all my solution is too slow.

Does anybody have a faster DP solution? Or can the bigints be handled faster?

Thanks, Erik

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden
My solution takes 0.006 secs and is not precalc, though it took me almost an hour to find a good recursion formula.

Hint 1: The even entries of your nsimple[]-array are simply the Catalan numbers, for which there is a simple recursion:
C_n = C_{n-1} * (4n-2)/(n+1), which follows from C_n = (2n choose n) / (n+1), which takes a bit of effort to prove.

Maniac
Experienced poster
Posts: 105
Joined: Tue Oct 14, 2003 3:24 pm
Location: Utrecht, Holland

### recursion relation found

Per,

I found a very simple function giving the desired number after doing some research on the internet: a(n) choose b(n) (where n is the value you read from input and a and b are very simple functions. I don't want to spoil too much).

But unfortunately I don't understand why this formula gives the correct result. I don't even see why the Catalan numbers give the nsimple-array. Could you perhaps explain why the Catalan numbers c[n] = (2n choose n)/(n+1) give the nsimple-array values?

Thanks, Erik

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden
I don't understand why my recursion formula gives the right result either, though I don't think it's a complete miracle. My recursion formula is very similar to the Catalan number recursion formula, and these trees are very similar to things that are counted by Catalan numbers. I basically found the formula by looking at small inputs/outputs and then guessing.

Why nsimple[] are the same as the Catalan numbers. The archetypical example of objects counted by Catalan numbers are well-balanced parenthesis expressions on n parenthesises. A binary tree can be converted into such an expression by doing an inorder traversal of the tree, and viewing edges going left as left parenthesises, and edges going right as right parenthesises. So "Tree 2" in the problem statement becomes "(())" and "Tree 3" becomes "()()". Some more work will also show that this is a bijection between the two sets of objects, so that they are indeed of equal size.

Hope that helps.

sumankar
A great helper
Posts: 286
Joined: Tue Mar 25, 2003 8:36 am
Location: calcutta
Contact:
Hi Per,
Your post was inspirational.I was fighting with the prob for some time, and
all of a sudden there it was, right in front of my eyes!

Thanks
Suman.[/java]

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

Although I solved this problem, I don't know why my method works.....
It would be great if someone can give me some comment.

Warning! Spoiler!

I find that the function f() have this pattern behind,
this let me to generate all the result quickly by computing f(i) from f(i-2)
with one bigInt multiplication and division, my code get accepted in 0.072s.

Code: Select all

f(2 ) = 1
f(4 ) = 3    f(4 )/f(2) = 3
f(6 ) = 10   f(6 )/f(4) = 3.333  3.333-3.0= 0.3333 = 1 / 3
f(8 ) = 35   f(8 )/f(6) = 3.5    3.5-3.333= 0.1667 = 1 / 6    6 - 3 = 3
f(10) = 126  f(10)/f(8) = 3.6    3.6-3.5  = 0.1000 = 1 / 10  10 - 6 = 4
f(12) = 462  f(12)/f(10)= 3.666  3.666-3.6= 0.0666 = 1 / 15  15 - 10= 5
My signature:
We can learn much more in discussion than reading source code.
• I HATE testing account.
• Don't send me source code for debug.

uzurpatorul
New poster
Posts: 5
Joined: Fri Oct 22, 2004 10:21 am
The formula is 1/2 * (m!)/((m/2)!*(m/2)!),
http://www.cs.brandeis.edu/~ira/papers/superballot.pdf

Niaz
Learning poster
Posts: 77
Joined: Fri Dec 17, 2004 11:06 am
Location: East West University, Dhaka, Bangladesh
Contact:
Why I am getting TLE ? Factorial Part takes 0.020 sec and the constant part takes rest of the time . How can it be possible ?

Code: Select all

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <math.h>
/* -------------------------- Big Integer Class -----------------------------*/
#define BASE   100000
#define MAX_DIGIT  1000
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))

typedef long INT;

class BigNum
{
private:
INT sign, len, digit[MAX_DIGIT];
void absSubtract(BigNum, BigNum);
public:
void operator  = (INT);             //ok
void operator  = (BigNum);          //ok
void operator  = (char *);          //ok
void subtract(BigNum, INT);         //ok-
void subtract(BigNum, BigNum);      //ok-
void mult(BigNum, INT);             //ok-
void mult(BigNum, BigNum);          //ok-
void div(BigNum, INT, INT &);       //ok- , third param is the remainder
void div(BigNum, BigNum, BigNum &); //ok-
INT comp(BigNum);                   //ok-
INT absComp(BigNum);                //ok-
void print();                       //ok-
void update();                      //ok-
void clear();                       //ok-
BigNum() {clear(); }
};

void BigNum :: operator = (INT x)
{
clear();
if(x < 0)
{
x = -x;
sign = 1;
}
if(x == 0)
{
digit[len++] = 0;
return;
}
while(x)
{
digit[len++] = x % BASE;
x /= BASE;
}
}

void BigNum :: operator = (BigNum n)
{
INT i;

clear();
len = n.len;
sign = n.sign;
//memset(digit, 0, sizeof(digit));
for(i = 0; i < len; ++i)
{
digit[i] = n.digit[i];
}
}

/*
while providing 's', ensure that there
are no leading spaces in it
*/
void BigNum :: operator = (char *s)
{
INT i, v, p;

clear();
p = 1;
i = strlen(s) - 1;
for(v = 0; i >= 0; i--)
{
if(s[i] == '-')
{
--i;
sign = 1;
break;
}
else if(s[i] == '+')
{
--i;
break;
}
if(s[i] < '0' || s[i] > '9' ) continue;
v = v + (s[i] - '0') * p;
p *= 10;
if(p == BASE)
{
digit[len++] = v;
p = 1;
v = 0;
}
}
if(v)
{
digit[len++] = v;
}
update();
}

/*
return value <===> meaning
0				equal
1				greater
-1				less
*/
INT BigNum :: comp(BigNum n)
{
INT i;

if(sign < n.sign)
{
return 1;
}
if(sign > n.sign)
{
return -1;
}
i = max(len, n.len) - 1;
for(; i >= 0; --i)
{
if(digit[i] > n.digit[i])
{
if(sign == 0)
{
return 1;
}
else
{
return -1;
}
}
}
return 0;
}

INT BigNum :: absComp(BigNum n)
{
INT i;

if(len < n.len)
{
return -1;
}
if(len > n.len)
{
return 1;
}
for(i = len - 1; i >= 0; --i)
{
if(digit[i] > n.digit[i])
{
return 1;
}
else if(digit[i] < n.digit[i])
{
return -1;
}
}
return 0;
}

void BigNum::absSubtract(BigNum a, BigNum b)
{
INT pos, borrow, t;

borrow = 0;
t = max(a.len, b.len);
for(pos = 0; pos < t; ++pos)
{
digit[pos] = a.digit[pos] - b.digit[pos] - borrow;
if(digit[pos] < 0)
{
digit[pos] += BASE;
borrow = 1;
}
else
{
borrow = 0;
}
if(digit[pos] != 0)
{
len = pos + 1;
}
}
update();
//assert(borrow == 0);//, "|B| > |A|; can't handle this");
}

{
INT pos, carry;

carry = 0;
for(pos = 0; pos < max(a.len, b.len); ++pos)
{
digit[pos] = a.digit[pos] + b.digit[pos] + carry;
carry = digit[pos] / BASE;
digit[pos] %= BASE;
}
if(carry != 0)
{
//check for overflow
digit[max(a.len, b.len)] = carry;
len = max(a.len, b.len) + 1;
}
else
{
len = max(a.len, b.len);
}
update();
}

void BigNum :: add(BigNum a, INT n)
{
BigNum t;

t = n;
}

void BigNum :: add(BigNum a, BigNum b)
{
clear();
if(a.sign == b.sign)
{
sign = a.sign;
}
else
{
if(a.absComp(b) >= 0)
{
absSubtract(a, b);
sign = a.sign;
}
else
{
absSubtract(b, a);
sign = b.sign;
}

}
}

void BigNum :: subtract(BigNum a, INT n)
{
BigNum t;

t = n;
subtract(a, t);
}

void BigNum :: subtract(BigNum a, BigNum b)
{
BigNum t;

clear();
t = b;
t.sign = 1 - b.sign;
}

void BigNum :: mult(BigNum a, INT s)
{
INT pos, carry;

if(s < 0)
{
sign = 1 - a.sign;
s = -s;
}
else
{
sign = a.sign;
}
carry = 0;
for(pos = 0; pos < a.len; ++pos)
{
digit[pos] = a.digit[pos] * s + carry;
carry = digit[pos] / BASE;
digit[pos] %= BASE;
}
pos = a.len;
while(carry != 0)
{
//check overflow
digit[pos] = carry % BASE;
carry /= BASE;
++pos;
}
len = pos;
update();
}

void BigNum :: multAndAdd(BigNum a, INT s, INT offset)
{
INT pos, carry;

carry = 0;
for(pos = 0; pos < a.len; ++pos)
{
digit[pos + offset] += a.digit[pos] * s + carry;
carry = digit[pos + offset] / BASE;
digit[pos + offset] %= BASE;
}
pos = a.len + offset;
while(carry != 0)
{
//check overflow
digit[pos] += carry;
carry = digit[pos] / BASE;
digit[pos] %= BASE;
++pos;
}
if(len < pos)
{
len = pos;
}
update();
}

void BigNum ::mult(BigNum a, BigNum b)
{
INT i, pos;

clear();
for(pos = 0; pos < b.len; ++pos)
{
}
sign = (a.sign + b.sign) % 2;
}

void BigNum :: div(BigNum a, INT s, INT &r)
{
INT pos;

r = 0;
len = 0;
sign = a.sign;
if(s < 0)
{
sign  = 1 - sign;
s = -s;
}
for(pos = a.len - 1; pos >= 0; --pos)
{
r = r * BASE + a.digit[pos];
digit[pos] = r / s;
if(digit[pos] > 0 && pos >= len)
{
len = pos + 1;
}
r %= s;
}
update();
}

void BigNum :: div(BigNum a, BigNum b, BigNum &r)
{
INT i, pos, lower, upper, mid;
BigNum d, e, t;

if(b.sign)
{
t = b;
t.sign = 0;
div(a, t, r);
sign = 1 - a.sign;
return;
}
for(i = 0; i < len; ++i)
{
digit[i] = 0;
}
len = 0;
r = (INT)0;
for(pos = a.len - 1; pos >= 0; --pos)
{
r.mult(r, BASE);
lower = 0;
upper = BASE - 1;
while(upper > lower)
{
mid = (upper + lower) / 2 + 1;
d.mult(b, mid);
e.subtract(r, d);
if(e.sign == 0)
{
lower = mid;
}
else
{
upper = mid - 1;
}
}
digit[pos] = lower;
d.mult(b, lower);
r.subtract(r, d);
if(digit[pos] > 0 && pos >= len)
{
len = pos + 1;
}
}
update();
}

void BigNum :: update()
{
while(len > 1 && digit[len - 1] == 0)
{
--len;
}
if(len <= 1 && digit[0] == 0)
{
sign = 0;
}
}

void BigNum :: clear()
{
sign = len = 0;
memset(digit, 0, sizeof(digit));
}

void BigNum :: print()
{
INT i;

if(sign) printf("-");
printf("%ld", digit[len - 1]);
for(i = len - 2; i >= 0; --i)
{
//BE CAREFUL HERE
switch(BASE)
{
case 10:
printf("%ld", digit[i]);
break;
case 100:
printf("%02ld", digit[i]);
break;
case 1000:
printf("%03ld", digit[i]);
break;
case 10000:
printf("%04ld", digit[i]);
break;
case 100000:
printf("%05ld", digit[i]);
break;
case 1000000:
printf("%06ld", digit[i]);
break;
case 10000000:
printf("%07ld", digit[i]);
break;
case 100000000:
printf("%08ld", digit[i]);
break;
case 1000000000:
printf("%09ld", digit[i]);
break;
default:
break;
}
}
}

/* ----------------------------------- Big Integer Class -----------------------------*/
BigNum Fact[610],M,R,H;
int main()
{
char st[10], ss[10];
long n,m,IN,CN;

st[0]='0';
st[1]=NULL;
ss[0]='1';
ss[1]=NULL;

Fact[0]=ss;
Fact[1]=ss;
/* Factorial Part */
for(n=1;n<=510;n++)
{
Fact[n+1].mult(Fact[n],n+1);
}
H=2;
scanf("%ld",&IN);
CN=1;
while(IN--)
{

/*Calculation in Constant Time*/
scanf("%ld",&n);
m=n/2;
M.div(Fact[n],Fact[m],R);
M.div(M,Fact[m],R);
M.div(M,H,R);
printf("Case %ld: ",CN);
CN++;
M.print();
printf("\n");
}
return 0;
}
Please join The ACM Solver Group at Yahoo
http://groups.yahoo.com/group/acm_solver/

abdul007
New poster
Posts: 1
Joined: Mon Feb 07, 2011 10:20 am

### Re: 10643 - Facing Problem With Trees

Niaz have you solved your problem which you were facing??

forthright48
New poster
Posts: 37
Joined: Wed Mar 14, 2012 11:57 am