Hi everyone, my name is Natalia and I'm a Software Engineer Manager at Google.
I work on Hiring products and also help out with Coding Competitions.
We hope you enjoyed all of the problems from our 2021 contest.
Today, Pablo and I are going to talk you through the problem Infinitree from the 2021 Code Jam finals.
Pablo, do you want to introduce yourself?
Hello Natalia, hello everyone.
My name is Pablo. I am a Software Engineer and work full time on Coding Competitions.
We will talk about what Infinitree asks us to do, and later discuss the solution a little bit.
Remember, you can always try any of our problems on your own at any time
in Practice Mode on g.co/CodeJam. Now, let's get started!
As you may have guessed, in Infinitree we will be working with a possibly infinite tree.
The tree is strictly binary, that is, every node has either 2 direct children or none.
Natalia, the input to the problem will still be finite right?
Yes Pablo, that’s a good point.
The tree is defined recursively from the root based on colours.
There is a finite number of colors. A white node has no children.
A node with a non-white color C has exactly two children,
a left child of color L_C and a right child of color R_C.
These L and R values are the input. The root has a fixed color Black.
Ok, so we generate the tree by starting with a black node at the root.
Then we attach two nodes with colors L_black and R_black to it.
Then we attach L_{L_black} and R_{L_black} to the left node, and so on.
Yes, as long as a node is non-white, it should eventually get its children attached to it by the process.
I see Natalia, so this process may never end and keep producing an infinite tree,
like the one on the left, but it can also end and produce a finite tree, like the example on the right.
Indeed. Then, we give numbers to the nodes of the tree from top to bottom and left to right.
So the root always has number 1, but other nodes have a number that does not depend solely on their colour,
as we now see in the example trees.
Exactly. We are now given two node numbers A and B.
We need to find the distance in the tree between them.
Distance between nodes in a tree? That sounds like an old and well studied problem to me.
Pablo, that is certainly true. But we have a case here where the node numbers
can be really large, up to 10 to the 18th!
Ok, so no building even just the relevant part of the tree in memory then.
Natalia, those huge numbers sound really hard to deal with.
They are. They are Code Jam Finals-hard, and maybe even more.
So, to solve the problem, we may need to work symbolically to avoid those huge structures that won't fit in memory.
The input already represents the infinite tree in a condensed way,
maybe we can do the same with the other objects we need.
That's a great idea Natalia. Remembering the way we built the tree before,
we can represent branches as paths on the directed graph implied by the L and R edges between colors.
The nodes at a particular level of the tree would be the ends of paths of a particular length.
Right, and paths of a length K in a directed graph can be counted by
powering the adjacency matrix of the graph to its K-th power. And powering matrices can be done efficiently.
It sounds like we could find out the level of the given nodes using bisection.
We just need to be able to count the number of nodes up to a certain level, not just exactly at one.
Natalia, I learned in school that you can efficiently compute the summation of all powers of a matrix with a divide and conquer technique.
Ok, Pablo, that helps us calculate, for any given level, how many nodes the tree has up to that level.
Using the bisection method (sometimes known as binary search),
we can get the first point at which that function is greater than the node numbers A or B, and know their level.
In Test Set 1 of the problem, node A is always the root,
which means the level of B is equal to the distance between them.
With the work we have done, we at least got some points out of this problem.
We must be on the right track, Pablo. Let's keep going.
If we know how to calculate the level of any node,
we can express the distance between A and B as the sum of their levels minus the level of their least common ancestor.
If we can compute that least common ancestor, we are done.
Yet another well studied problem, but on a gigantic tree.
Speaking about typical work on trees, the way you usually work on them is by going into subtrees.
However, the node numbering is a problem, because a node's number is affected by all nodes, so it is hard to adjust it when moving to a subtree.
We could try to use a better naming system for nodes. For example, we could use a pair of numbers
consisting of the level that we already know how to calculate, and the offset, that is, the number of nodes to the left, at the same level.
Like a coordinate system. We already know how to calculate levels given a node number,
and we can calculate the initial offset as the difference between the node number and the number of nodes up to the previous level.
Ok Pablo, so, a node at level K and with X nodes on its left
would be the node at level K-1 with the same offset in the left subtree.
But what about moving to the right subtree?
We would have to subtract from X the number of nodes at the same level that were left behind.
Counting that offset difference sounds similar to what we have already done.
It is exactly the number of paths of length K that start at the root color.
We can also use the K-th power of the adjacency matrix for that!
I see. So, if the number of nodes in the left subtree at level K-1 is at least X,
that means the node represented by (K, X) is on the left subtree. If not, it is on the right.
You can turn that into an algorithm by simply moving down from the root
as long as both input nodes are on the same subtree.
Once they are not, the current root is their lowest common ancestor so the sum of their levels is the answer.
Nice observation Natalia. That can help us solve more cases than before,
but only when the lowest common ancestor is not too far from the root. Otherwise, this will take a long time!
That's true Pablo. On many trees, the level of a node
is just logarithmic on its node number, and this solution will work.
Maybe we can move multiple steps at once in the other cases?
For the number of nodes not to grow exponentially, each color from the input graph must be in at most one cycle.
We should be able to process multiple passes through those cycles efficiently, generalizing what we did to process a single step.
I think you are right, Pablo, but we don't have time for all the details here.
A detailed description of the entire solution is available in the analysis tab of the problem page.
It is already available at g.co/codejam.
Stopping sounds like the right call. Thanks for watching everyone, we hope you enjoyed it!
Remember to check out our videos for the other finals' problems.
Bye Pablo, bye everyone. Good bye.