10643 - Facing Problem With Trees

[football2001]

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

[Maniac]

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]

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]

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]

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]

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]

[..]

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

[uzurpatorul]

The formula is 1/2 * (m!)/((m/2)!*(m/2)!),
http://www.cs.brandeis.edu/~ira/papers/superballot.pdf

[Niaz]

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 absAdd(BigNum, BigNum);
    void absSubtract(BigNum, BigNum);
    void multAndAdd(BigNum, INT, INT);
public:
	void operator  = (INT);             //ok
    void operator  = (BigNum);          //ok
    void operator  = (char *);          //ok
    void add(BigNum, INT);              //ok-
    void add(BigNum, BigNum);           //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");
}

void BigNum::absAdd(BigNum a, BigNum b)
{
	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;
    add(a, t);
}

void BigNum :: add(BigNum a, BigNum b)
{
    clear();
    if(a.sign == b.sign)
    {
	absAdd(a, b);
	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;
    add(a, t);
}

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)
    {
	//take care about any overflow
	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)
    {
	multAndAdd(a, b.digit[pos], 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);
	r.add(r, a.digit[pos]);
	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;
}

[abdul007]

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

[forthright48]

I knew there was a relation between total number of binary tree and catalan number, but I failed to find the relation with Balance binary tree. In the end I constructed a dp solution that took a long time to calculation the answer and then simply hard coded the answers into the solution :p