Connection Status:
Competition Arena > HatRack

HatRack

SRM 559 · 2012-06-05 · by tehqin

SRM 559 · 2012-06-05 · by tehqin · Graph Theory, Recursion
Class Name: HatRack
Return Type: long
Method Name: countWays
Arg Types: (vector<int>, vector<int>)
Problem Statement

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.

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

Submissions are judged against all 174 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class HatRack with a public method long long countWays(vector<int> knob1, vector<int> knob2) · 174 test cases · 2 s / 256 MB per case

Submitting as anonymous