Infinitree codejam solution
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, or a node with two trees attached to it: a left subtree and a right subtree. In both cases, 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 .
There is a set of colors numbered fromto , inclusive. Each node is of exactly one color. There might be zero, one, or multiple nodes of each color. Each node of color (white) is a leaf node (that is, it has no children). Each node of color , for , has exactly children: the left one is color and the right one is color . The root of the tree is color (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 listsand . Color is blue and color is yellow.
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. 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.
As another example, the following picture shows the firstnodes of an infinite tree defined by the lists and . Color is green.
Given the listsand that define a tree and the indices of two different nodes in the tree, return the distance between those two nodes.
The first line of the input gives the number of test cases,. test cases follow. Each test case consists of three lines. The first line contains , , and : 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 integers and the third line contains integers , as described above.
For each test case, output one line containing
Case #, where : is the test case number (starting from 1) and is the distance between the nodes with indices and in the tree defined by the lists and .
Time limit: 90 seconds.
Memory limit: 1 GB.
The tree defined by and has at least nodes.
Test Set 1 (Visible Verdict)
Test Set 2 (Hidden Verdict)
Note: there are additional samples that are not run on submissions down below.
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
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.
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
Case #1: 4 Case #2: 3 Case #3: 5 Case #4: 8