I, ME AND MYSELF !!!: usaco

Friday, December 21, 2012

USACO 3.3 fence

Section 3.3: Riding the Fences

This is just another simple Euler path problem. Given a undirected unweighted graph, which contains multiple edges, you have to find the lexicographically smallest Euler path.

I don't know what the problem setter was thinking, but he made a big mistake. Problem statement says "Your program must output the path of intersections that, if interpreted as a base 500 number, would have the smallest magnitude." where nodes are numbered from 1 to 500. Clearly, 500 is not a base 500 digit. I made several wrong submissions for trying to do some foolish tricks to get this done, then I just did a lexicographic ordering, and it passed. Pretty funny!

Problem statement ensures that there is no input for which Euler path does not exist. This makes the solution easier, just check if all the degrees are even, if so, start from the smallest numbered node, otherwise start from smaller numbered odd degree node.

 algorithm for finding euler path: graph[u][v] contains number of edges between u and v  find( node u ):     for each adjacent v of u in lexicographical order:         while( graph[u][v] > 0 ):             graph[u][v]--;             graph[v][u]--;             find(v);     stack.push(u);

Now the stack contains the euler path in reverse order, so just keep popping!

Wednesday, August 4, 2010

Binary Tree -- N Nodes & H Height

The problem:

You are told that you have N unique numbers, how many different binary trees are possible with those N numbers (i.e. nodes) which has exactly H height.

Analysis:

If we look closely, it will be not that hard to figure out that, the problem actually wants to know, how many different binary trees are possible to build with N nodes, each of which has exactly H height allowing rotations. Here, two trees are different when their structures are different. For example:


           @                   @
          / \                 / \
         @   @      and      @   @
        / \                     / \
       @   @                   @   @

Solution:

I don't know whether this problem has a mathematical solution or not, I have searched for it and found nothing... But, if the values N and H supports, this problem can be solved with a dynamic programming approach.

When we want to build a tree with N nodes and H height, we can select a node as a root, so, we can put 1 to N-2 nodes on the left subtree of height H-1 or less and N-2 to 1 nodes on the right subtree of height H-1 or less, satisfying that, at least one of the subtree has a height H-1. So, by using proper base condition, we can find the number of different trees of exactly H height from this recursive formulation, and we can express the relation as follows,


if k == 1 then exactTrees( N, D ) = ( n == 1 )
if n <= 1 then exactTrees( N, D ) = 0
for all {L, R} such that L, R > 0 and L + R = N - 1:
exactTrees( N, D ) += exactTrees( L, D - 1 ) * exactTrees( R, D - 1 )
exactTrees( N, D ) += smallerTrees( L, D - 2 ) * exactTrees( R, D - 1 )
exactTrees( N, D ) += exactTrees( L, D - 1 ) * smallerTrees( R, D - 2 )

This is pretty obvious, because, if we want to get a tree of height H from any node, either one or both of its subtrees must have a height H - 1, and if we have N nodes at any step, we need to take 1 node as root, and then if we take i nodes for left subtree, we have N - 1 - i nodes left for the right subtree.
When we calculate exact height, we need to consider that a subtree may have a smaller height, so we need to calculate smallerTrees( N, D ) separately, but actually it is a bit easier:


if n < 0 or k <= 0 then smallerTrees( N, D ) = 0
if k == 1 then smallerTrees( N, D ) = ( n == 1 )
if n <= 1 then smallerTrees( N, D ) = 1
else
for all {L, R} such that L, R > 0 and L + R = N - 1:
smallerTrees( N, D ) += smallerTrees( L, D - 1 ) * smallerTrees( R, D - 1 )

Sample program:

First one goes the recursive algorithm (with dp):


// states: nodes, height
int exact[202][101], smaller[202][101];

int smallTrees(int n, int k)
{
    if(n<0 || k<=0) return 0;
    if(k==1) return n==1;
    if(n<=1) return 1;
 
    int &ret = smaller[n][k], l, r;
    if(ret!=-1) return ret;
 
    ret = 0;
    for(int i=1; i<n-1; i++)
    {
        l = i, r = n-1-i;
        if(l && r)
        {
            ret += smallTrees(l, k-1)*smallTrees(r, k-1);
        }
    }
    return ret;
}

int exactTrees(int n, int k)
{
    if(k==1) return n==1;
    if(n<=1) return 0;

    int &ret = exact[n][k], l, r;
    if(ret!=-1) return ret;
    ret = 0;
    for(int i=1; i<n-1; i++)
    {
        l = i, r = n-1-i;
        if(l && r)
        {
            ret += exactTrees(l, k-1)*exactTrees(r, k-1);
            ret += exactTrees(l, k-1)*smallTrees(r, k-2);
            ret += smallTrees(l, k-2)*exactTrees(r, k-1);
        }
    }
    return ret;
}

Here is the iterative version (a little complex):


// states: height, nodes
int exactTrees[101][202], smallTrees[101][202];

void solve(int n, int k)
{
    int d, i, j;
    exactTrees[1][1] = 1;
    for(d=2; d<=k; d++) // depth
    {
        for(i=1; i<=n; i+=2) // number of nodes
        {
            for(j=1; j<=i-1; j+=2) // left & right
            {
                exactTrees[d][i] += exactTrees[d-1][j]*exactTrees[d-1][i-1-j];
                exactTrees[d][i] += exactTrees[d-1][j]*smallTrees[d-2][i-1-j];
                exactTrees[d][i] += smallTrees[d-2][j]*exactTrees[d-1][i-1-j];
            }
        }
        for(i=1; i<=n; i+=2) // update smaller tree
        {
            smallTrees[d-1][i] += smallTrees[d-2][i]+exactTrees[d-1][i];
        }
    }
}

[P.S. The result of this problem grows very rapidly along with the increase of N and H, so, it may easily run out of range, normally problems like this requires the result with respect to some modulus values.]