JOIN
Get Time

   Problem Statement  

 Problem Statement for HatRack

Problem Statement

    The Order of the Hats has commissioned the creation of a new hat rack. This new hat rack must meet certain properties in order to be considered to hold headwear of such importance. The hat rack is formed by taking several numbered knobs that are connected by rods. One of the knobs is nailed to the wall. The remaining knobs then hang below this top knob. A sample hat rack is shown in the picture below.







The picture also shows that the hat rack can be divided into levels of knobs. Formally, the level i is defined to contain each knob X such that there are exactly i rods between the top knob and knob X.



The order would like their hat rack to meet the following three requirements:
  1. Each knob X can have at most two knobs hanging directly below it. If there is only one such knob, it hangs directly below X; otherwise, one knob will hang slightly to the right of X and the other slightly to the left.
  2. Except for the bottommost level, each level must be full. That is, if level i is not the bottommost level, it must contain exactly 2^i knobs.
  3. The bottommost level must have all its knobs as far on the left as possible.


The third requirement in more detail: Let b be the bottommost level. If we traverse level b-1 from left to right, there will first be some knobs with two rods going to knobs in level b, then possibly a single knob with one rod going to level b, and finally some knobs not connected to any knob in level b.



You are given a configuration of knobs and rods. The knobs are not fastened to the wall yet. The knobs are numbered 1 through N. There are precisely N-1 rods, and they are connecting the knobs in such a way that the entire structure holds together. (Thus, necessarily, the topology of the hat rack is a tree.)



You are given two int[]s knob1 and knob2, each containing N-1 elements. These two int[]s describe the rods: For each i, there is a rod connecting the two knobs knob1[i] and knob2[i]. Return the number of ways to arrange the hat rack such that it meets the requirements set by the Order of the Hats. Two arrangements are considered different if the relative position of at least one pair of knobs differs. If it is not possible to meet the requirements, return 0.
 

Definition

    
Class:HatRack
Method:countWays
Parameters:int[], int[]
Returns:long
Method signature:long countWays(int[] knob1, int[] knob2)
(be sure your method is public)
    
 

Notes

-The correct number of arrangements always fits in a signed 64 bit integer.
 

Constraints

-knob1 will contain between 1 and 50 elements, inclusive.
-knob1 and knob2 will contain the same number of elements.
-Each element of knob1 will be between 1 and N, inclusive, where N is 1 + (the number of elements in knob1).
-Each element of knob2 will be between 1 and N, inclusive, where N is 1 + (the number of elements in knob2).
-Each pair of knobs in the hat rack will be connected by some sequence of rods and knobs.
 

Examples

0)
    
{1}
{2}
Returns: 2
1)
    
{1,1}
{2,3}
Returns: 2
2)
    
{1,1,1,1}
{2,3,4,5}
Returns: 0
3)
    
{6,6,6,4,1}
{1,2,4,5,3}
Returns: 0
4)
    
{1,1,2,2,11,11,8,8,3,3,4,4,5}
{2,3,11,8,12,13,9,10,4,5,7,6,14}
Returns: 16
5)
    
{1,2,3,4,5,6,7,8,9}
{2,3,4,5,6,7,8,9,10}
Returns: 0

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.

This problem was used for:
       Single Round Match 559 Round 1 - Division I, Level Two