10643 - Facing Problem With Trees

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

Moderator: Board moderators

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

10643 - Facing Problem With Trees

Post by football2001 » Wed May 05, 2004 8:59 am

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?

Post by Maniac » Fri May 07, 2004 12:16 pm

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

Post by Per » Fri May 07, 2004 1:08 pm

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

Post by Maniac » Fri May 07, 2004 4:44 pm

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

Post by Per » Fri May 07, 2004 6:41 pm

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:

Post by sumankar » Sat May 08, 2004 6:58 am

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

Post by .. » Wed Sep 22, 2004 9:13 am

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:
  • 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.

uzurpatorul
New poster
Posts: 5
Joined: Fri Oct 22, 2004 10:21 am

Post by uzurpatorul » Tue Oct 26, 2004 1:05 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:

Post by Niaz » Fri Dec 17, 2004 9:04 pm

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;
}
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

Post by abdul007 » Mon Feb 07, 2011 10:56 am

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

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

Re: 10643 - Facing Problem With Trees

Post by forthright48 » Wed Mar 19, 2014 9:08 pm

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
What ever happens, happens for good. Even when we get WA :p
http://www.forthright48.com

Post Reply

Return to “Volume 106 (10600-10699)”