Editorial for New Year's '18 P5 - Hanoi Heuristics

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: Eliden

For the first subtask, it suffices to give a Hamiltonian path of all arrangements with $N$ ~N~ pegs. This can be done in a number of ways. For instance, one can define a recursive function $f(i,r)$ ~f(i,r)~ that keeps the disks larger than $i$ ~i~ fixed, but visits all possible arrangements with this restriction. If $r=0$ ~r=0~, the first $i$ ~i~ disks are assumed to be in pile $1$ ~1~, and are moved to pile $3$ ~3~, and if $r=1$ ~r=1~, the disks are all moved from pile $3$ ~3~ to pile $1$ ~1~.

Complexity: $\mathcal O(3^N)$ ~\mathcal O(3^N)~

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 $a$ ~a~ to pile $b$ ~b~, where $c$ ~c~ is the third pile, recursively "move" all smaller disks to pile $c$ ~c~, then output the command $a b$ ~a b~. The complexity of moving between two arrangements using this approach is bounded $\mathcal O(2^d)$ ~\mathcal O(2^d)~, where $d$ ~d~ 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 $\mathcal O(2^N)$ ~\mathcal O(2^N)~.

Complexity: $\mathcal O(2^N Q)$ ~\mathcal O(2^N Q)~

The third subtask builds on the idea of the second, taking advantage of the bound $\mathcal O(2^d)$ ~\mathcal O(2^d)~. 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 $\mathcal O(2^{N-\log_3(Q)}Q)=\mathcal O(2^N Q^{1-\log_3(2)})=\mathcal O(2^N Q^{0.37})$ , a significant improvement. One can prove this as follows. Imagine a complete ternary tree of height $N$ ~N~. Here, the leaf nodes are arrangements we want to visit, and the rooted subtrees of height $d$ ~d~ represent sets of arrangements with the largest $N-d$ ~N-d~ disks fixed. Moving between two leaf nodes in a subtree of height $d$ ~d~ has cost at most $\mathcal O(2^d)$ ~\mathcal O(2^d)~. Define the "power" of a node to be $2^d$ ~2^d~, where $d$ ~d~ 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 $Q$ ~Q~ leaf nodes. Note that there can be at most distinct $Q$ ~Q~ 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 $2^{N-\log_3(Q)}$ ~2^{N-\log_3(Q)}~, and it turns out that the overall sum will be at most $2^{N-\log_3(Q)}Q$ ~2^{N-\log_3(Q)}Q~, as desired.

Note that this approach generalizes so that if the tree is $b$ ~b~-ary and the powers decrease by factors of $a$ ~a~ as one goes down the tree, the complexity will be $N Q^{1-1/\log_a(b)}$ ~N Q^{1-1/\log_a(b)}~, where $N$ ~N~ is now the power of the root node. There are a few interesting things to remark here. First, $\log_a(b)$ ~\log_a(b)~ is what is called a "Hausdorff Dimension". So, one might loosely say that we have a way to traverse $Q$ ~Q~ points in an object of size $N$ ~N~ and Hausdorff Dimension $x$ ~x~ with complexity $\mathcal O(N Q^{1-1/x})$ ~\mathcal O(N Q^{1-1/x})~. Since the Hausdorff Dimension of the Sierpinski Triangle, which has a deep connection with the Tower of Hanoi, is $\log_2(3)$ ~\log_2(3)~, this checks out with our particular problem here. More commonly, we may want to visit $Q$ ~Q~ points in an $N$ ~N~ by $N$ ~N~ grid. In this case, the Hausdorff Dimension is $2$ ~2~, and there is indeed a way to visit $Q$ ~Q~ points in time $\mathcal O(N Q^{1-1/2})=\mathcal O(N\sqrt{Q})$ . To do this in practice, one can sort points $(x,y)$ ~(x,y)~ by interleaving the bits in the binary representation of $x$ ~x~ and $y$ ~y~. 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: $\mathcal O(2^N Q^{0.37})$ ~\mathcal O(2^N Q^{0.37})~

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 $\mathcal O(N)$ ~\mathcal O(N)~ time (the number being the number of the move in the Hamiltonian path which visits the arrangement), then sorting by these numbers.

Complexity: $\mathcal O(2^N Q^{0.37})$ ~\mathcal O(2^N Q^{0.37})~

Comments

1

SamZhangQingChuan commented on Jan. 5, 2018, 7:20 a.m.

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!

2
Eliden commented on Jan. 6, 2018, 3:56 p.m. ← edited →
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 $\mathcal{O}(N)$ ~\mathcal{O}(N)~ time for each of the $Q$ ~Q~ arrangements:

int acc=0, pow=1; for(int i=0; i<n; ++i) { if(s[i]=='2') acc = 2*pow-1-acc; else acc += pow*(s[i]-'1'); pow *= 3; }

0

SamZhangQingChuan commented on Jan. 8, 2018, 7:19 a.m.

how do you prove it's a Hamiltonian path?

2

Eliden commented on Jan. 8, 2018, 1:17 p.m. ← edited →

We can prove it using induction on the number of disks. For $N = 0$ ~N = 0~, the sequence contains one arrangement, so it is a Hamiltonian path. Now consider what the sequence will be like for $N > 0$ ~N > 0~. If $A$ ~A~ represents the largest disk, and $B$ ~B~ represents the $N-1$ ~N-1~ smaller disks stacked onto each other, and $\emptyset$ ~\emptyset~ denotes an empty pile, then our sequence is made up of the parts $(AB,\emptyset,\emptyset), \dots, (A,\emptyset,B)$ and $(\emptyset,A,B), \dots, (B,A,\emptyset)$ and $(B,\emptyset,A), \dots, (\emptyset,\emptyset,AB)$ , in that order. The largest disk $A$ ~A~ 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 $(A,\emptyset,B)$ ~(A,\emptyset,B)~ and $(\emptyset,A,B)$ ~(\emptyset,A,B)~, as well as between $(B,A,\emptyset)$ ~(B,A,\emptyset)~ and $(B,\emptyset,A)$ ~(B,\emptyset,A)~ (all other movements are accounted for using induction). These two movements are allowed because all $N-1$ ~N-1~ 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.