Infinitree solution codejam

Infinitree codejam solution

For Solution

Click Here!

This problem is about finding the distance between two nodes of a strictly binary tree. Oh, is that too easy?! Ok, the tree is potentially infinite now. Keep it up and we will start going up the aleph numbers.

In this problem, a tree is either a single node XX, or a node XX with two trees attached to it: a left subtree and a right subtree. In both cases, XX is the root of the tree. If the tree is not a single node, the roots of both the left and right subtrees are the only children of XX.

There is a set of colors numbered from 00 to NN, inclusive. Each node is of exactly one color. There might be zero, one, or multiple nodes of each color. Each node of color 00 (white) is a leaf node (that is, it has no children). Each node of color ii, for 1iN1≤i≤N, has exactly 22 children: the left one is color LiLi and the right one is color RiRi. The root of the tree is color 11 (black). Note that the tree may have a finite or countably infinite number of nodes.

For example, the following picture illustrates a finite tree defined by the lists L=[3,0,0]L=[3,0,0] and R=[2,0,2]R=[2,0,2]. Color 22 is blue and color 33 is yellow.

A tree with colored nodes

The distance between two nodes in the tree is the minimum number of steps that are needed to get from one node to the other. A step is a move from a node to its direct parent or its direct child.

Nodes in the tree are indexed using positive integers. The root has index 11. Then, other nodes are indexed using consecutive integers, with nodes with smaller distances to the root being indexed first. For nodes that are equidistant to the root, nodes that are further to the left are indexed first. For example, the following picture adds indices to each node in the tree we presented before. Notice that each node’s index is independent from its color.

A tree with colored and indexed nodes

As another example, the following picture shows the first 3333 nodes of an infinite tree defined by the lists L=[3,4,2,4]L=[3,4,2,4] and R=[2,2,4,0]R=[2,2,4,0]. Color 44 is green.

An infinite tree with colored and indexed nodes

Given the lists LL and RR that define a tree and the indices of two different nodes in the tree, return the distance between those two nodes.

Input

The first line of the input gives the number of test cases, TTTT test cases follow. Each test case consists of three lines. The first line contains NNAA, and BB: the size of the lists that define the tree, and the indices of the two nodes whose distance you need to calculate, respectively. The second line contains NN integers L1,L2,,LNL1,L2,…,LN and the third line contains NN integers R1,R2,,RNR1,R2,…,RN, as described above.

Output

For each test case, output one line containing Case #xxyy, where xx is the test case number (starting from 1) and yy is the distance between the nodes with indices AA and BB in the tree defined by the lists LL and RR.

Limits

Time limit: 90 seconds.
Memory limit: 1 GB.
1T1001≤T≤100.
1N501≤N≤50.
0LiN0≤Li≤N.
0RiN0≤Ri≤N.
A<B1018A<B≤1018.
The tree defined by LL and RR has at least BB nodes.

Test Set 1 (Visible Verdict)

A=1A=1.

Test Set 2 (Hidden Verdict)

1A10181≤A≤1018.

Sample

Note: there are additional samples that are not run on submissions down below.

Sample Input
content_copy
5
3 1 8
3 0 0
2 0 2
3 1 5
3 0 0
2 0 2
4 1 27
3 4 2 4
2 2 4 0
4 1 28
3 4 2 4
2 2 4 0
3 1 10
1 3 1
3 2 1
Sample Output
content_copy
Case #1: 3
Case #2: 2
Case #3: 4
Case #4: 5
Case #5: 3

The tree in Sample Cases #1 and #2 is the first tree shown in the statement. The tree in Sample Cases #3 and #4 is the last tree shown in the statement. The same is true for the additional samples below. In Sample Case #5, notice that some colors may not be present in the tree.

 

Additional Sample – Test Set 2

The following additional sample fits the limits of Test Set 2. It will not be run against your submitted solutions.

Sample Input
content_copy
4
3 5 7
3 0 0
2 0 2
3 4 9
3 0 0
2 0 2
4 11 18
3 4 2 4
2 2 4 0
4 21 22
3 4 2 4
2 2 4 0
Sample Output
content_copy
Case #1: 4
Case #2: 3
Case #3: 5
Case #4: 8

For Solution

Click Here!

Leave a Reply

Your email address will not be published. Required fields are marked *

*