Editorial for New Year's '18 P5 - Hanoi Heuristics
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
For the first subtask, it suffices to give a Hamiltonian path of all arrangements with pegs. This can be done in a number of ways. For instance, one can define a recursive function
that keeps the disks larger than
fixed, but visits all possible arrangements with this restriction. If
, the first
disks are assumed to be in pile
, and are moved to pile
, and if
, the disks are all moved from pile
to pile
.
Complexity:
For the second subtask, it is enough to visit the arrangements in a random order, using a relatively direct way to go from one arrangement to another. Going between two arrangements can be done by distilling the key ideas from the classic Tower of Hanoi puzzle. To move a disk from pile to pile
, where
is the third pile, recursively "move" all smaller disks to pile
, then output the command
. The complexity of moving between two arrangements using this approach is bounded
, where
is the largest disk that needs to be moved at all. However, by visiting the arrangements in random order, the best that can be guaranteed is
.
Complexity:
The third subtask builds on the idea of the second, taking advantage of the bound . The only major difference from the solution to the previous subtask is that the arrangements are sorted in a particular order using a heuristic that gives a better complexity. This order is, namely, right-to-left lexicographical order of the input. Intuitively, this order is advantageous because it minimizes the movement of the larger disks, which are the most expensive to move.
This ordering, perhaps surprisingly, gives the complexity , a significant improvement.
One can prove this as follows.
Imagine a complete ternary tree of height
.
Here, the leaf nodes are arrangements we want to visit, and the rooted subtrees of height
represent sets of arrangements with the largest
disks fixed.
Moving between two leaf nodes in a subtree of height
has cost at most
.
Define the "power" of a node to be
, where
is the height of the subtree rooted at that node.
Our strategy is to visit the nodes in the inorder of the tree.
The cost to move from one leaf node to the next is proportional to the power of the lowest common ancestor of the two nodes.
Call a node "critical" if it is the lowest common ancestor of some two of the
leaf nodes.
Note that there can be at most distinct
critical nodes.
Then, the total cost will be proportional to the sum of the powers of the critical nodes.
In the worst case, the critical nodes are as high up in the tree as possible (as this maximizes the powers of the critical nodes).
In this case, most of the critical nodes will have power
, and it turns out that the overall sum will be at most
, as desired.
Note that this approach generalizes so that if the tree is -ary and the powers decrease by factors of
as one goes down the tree, the complexity will be
, where
is now the power of the root node.
There are a few interesting things to remark here. First,
is what is called a "Hausdorff Dimension".
So, one might loosely say that we have a way to traverse
points in an object of size
and Hausdorff Dimension
with complexity
. Since the Hausdorff Dimension of the Sierpinski Triangle, which has a deep connection with the Tower of Hanoi, is
, this checks out with our particular problem here.
More commonly, we may want to visit
points in an
by
grid.
In this case, the Hausdorff Dimension is
, and there is indeed a way to visit
points in time
.
To do this in practice, one can sort points
by interleaving the bits in the binary representation of
and
.
Alternatively, sorting points by the order they would be visited by the Hilbert space-filling curve has the same effect.
This technique has the same complexity, and can be used in the same situations, as the well-known Mo's Algorithm.
Complexity:
The final subtask tests a small constant optimization from the third subtask.
The key idea is that although sorting the arrangements directly as in the previous subtask is good asymptotically, it doesn't really reflect an elegant path through the Tower of Hanoi graph.
The intended solution is to visit the points in the same order they would be visited by the Hamiltonian path given in the first subtask.
This can be done by calculating a representative number for each arrangement in time (the number being the number of the move in the Hamiltonian path which visits the arrangement), then sorting by these numbers.
Complexity:
Comments
still confused... How do you calculate
the number being the number of the move in the Hamiltonian path which visits the arrangement
? Thanks in advance!In case it wasn't clear, the intended Hamiltonian path is the one which visits arrangements with the largest disk in pile 1, then the arrangements with the largest disk in pile 2, but in reverse, then the arrangements with the largest disk in pile 3. To get the required index of an arrangement, some solutions precomputed the entire ordering, but the following direct approach only takes
time for each of the
arrangements:
how do you prove it's a Hamiltonian path?
We can prove it using induction on the number of disks. For
, the sequence contains one arrangement, so it is a Hamiltonian path. Now consider what the sequence will be like for
. If
represents the largest disk, and
represents the
smaller disks stacked onto each other, and
denotes an empty pile, then our sequence is made up of the parts
and
and
, in that order. The largest disk
doesn't interfere with movements of smaller disks, so the three parts are individually Hamiltonian paths on the subset of arrangements with the largest disk in a particular pile. Because of these properties, it is clear that the overall sequence will visit every arrangement exactly once. To see that the sequence is in fact a path, we need to check that we can move between
and
, as well as between
and
(all other movements are accounted for using induction). These two movements are allowed because all
smaller disks are in a separate pile where they do not interfere with the movement of the largest disk. So by induction, we are done.