Internet Problem Solving Contest

• Correct output for F1
• Correct output for F2
• Python 3 program solving both subproblems
• Python 3 program to check submissions

The algorithms from this problem have originally been devised for another task: card shuffling. There are two ways to perform a perfect riffle shuffle of a deck of cards. (In one of those ways the top card remains on the top, in the other way it becomes the second card from the top.) These two ways of shuffling change the order of a deck of cards in exactly the same way our ferries change the order of the cars in the convoy.

The question from the problem statement then becomes a very natural question: what is the smallest number of (carefully chosen and perfectly executed) riffle shuffles to get a particular card from position p to position q in the deck?

A nice solution to this problem is described by Sarnath Ramnath and Daniel J. Scully in their paper “Moving card i to position j with perfect shuffles”.

The general idea of this solution is very simple. Let’s use zero-based indexing, i.e., cards have numbers 0 through 2n − 1. Counting modulo 2n, a card from position i can go to either 2i or 2i + 1. If we start to draw a tree of possibilities, we will quickly realize that after k shuffles the reachable numbers are precisely those in the interval [i ⋅ 2^k, (i + 1)⋅2^k − 1]. (Of course, still counting modulo 2n. As soon as the length of this interval reaches 2n, any value is possible.)

Thus, we have a very simple solution:

• Increment k until our interval hits the desired destination. (This takes O(logn) steps.)
• From the binary value of the offset your destination has within the interval (i.e., from the value “destination minus left boundary of the interval”), reconstruct the right sequence of “times two” and “times two plus one” that gets you from your source to your destination.
• For each individual operation, determine whether it is done by an out-shuffle or an in-shuffle (i.e., an R-ferry or an L-ferry).