Shuffling Cards with Problem Solver 68!

We need choose a cyclic cut first, then apply $t$ perfect riffles, and among all choices output the lexicographically smallest final deck.

The annoying part is that the shuffle is global. The nice part is that $n=2^k$, which means positions are secretly just bitstrings wearing a trench coat.

What one riffle does

Use $0$-indexed positions. Let $n=2^k$ and $h=n/2$.

One riffle maps an old position $i$ to:

$$\begin{cases} 2i,& i<h,\\ 2(i-h)+1,& i\ge h. \end{cases}$$

Write $i$ as a $k$-bit number. This transformation moves the most significant bit to the least significant bit. In other words, it is a left cyclic rotation of the $k$ position bits by $1$.

So after $t$ riffles, the old position $i$ moves to

$\operatorname{rotL}(i,r),\qquad r=t\bmod k.$

Equivalently, the character at final position $p$ came from pre-shuffle position

$\operatorname{rotR}(p,r).$

Now include Mutsuki's cut. If she cuts by $m$, the pre-shuffle deck is

$d_m[j]=d[(j+m)\bmod n].$

Therefore the final string for cut $m$ is:

$$A_m[p]=d[(\operatorname{rotR}(p,r)+m)\bmod n].$$

So the whole problem becomes:

Among all $m\in[0,n)$, find the lexicographically smallest string obtained by reading cyclic string $d$ at offsets $m+x_0,m+x_1,\ldots,m+x_{n-1},$ where $x_p=\operatorname{rotR}(p,r)$.

Brute force would compare $n$ strings of length $n$, which is $O(n^2)$. With $n=2^{18}$, that is very much in “your CPU files a complaint” territory.

Ranking prefixes

We can rank all cuts by prefixes of length $1,2,4,\ldots,n$ in this shuffled order.

Let $rank_q[m]$ mean the rank of the length-$2^q$ prefix of $A_m$:

$$(d[m+x_0],d[m+x_1],\ldots,d[m+x_{2^q-1}]).$$

Equal ranks mean equal prefixes. Smaller rank means lexicographically smaller prefix.

Initially,

$rank_0[m]=d[m].$

Now suppose we know ranks for length $2^q$. To get length $2^{q+1}$, split the prefix into two halves:

$$A_m[0..2^{q+1}) = A_m[0..2^q) + A_m[2^q..2^{q+1}).$$

The first half has rank $rank_q[m]$.

What about the second half? Its offsets are

$$x_{p+2^q}=\operatorname{rotR}(p+2^q,r).$$

For $0\le p<2^q$, adding $2^q$ just sets bit $q$ of $p$. Rotating right by $r$ moves that bit to position

$$(q-r)\bmod k.$$

So the second half is exactly the same length-$2^q$ pattern, but shifted by

$$2^{(q-r)\bmod k}.$$

Therefore:

$$rank_{q+1}[m] =\operatorname{compress}\left(rank_q[m],\ rank_q[(m+2^{(q-r)\bmod k})\bmod n]\right).$$

This is suffix-array doubling, except the shift order is dictated by the riffle. Same weapon, weirder battlefield.

Why compression works

The length-$2^{q+1}$ key for cut $m$ is the concatenation of two length-$2^q$ keys. If we already know the lexicographic ranks of all length-$2^q$ keys, then comparing two longer keys is just comparing pairs:

$$(rank_q[\text{first half}], rank_q[\text{second half}]).$$

Sort these pairs and assign compressed ranks. Since ranks are small integers, this can be done with two stable counting-sort passes. This preserves both ordering and equality. No hashing needed, no collision nonsense. Hashing is cool until it betrays you at 2 AM.

After $k$ rounds, the prefix length is $2^k=n$, so $rank_k[m]$ ranks the entire final deck produced by cut $m$. Pick any $m$ with minimum rank.

Constructing the answer

Once we know the best cut $m$, build the actual string directly:

$$ans[p]=d[(m+\operatorname{rotR}(p,r))\bmod n].$$

Complexity

There are $k\le18$ rounds. Each round does linear counting-sort work over $n\le262144$ cuts.

$O(kn)$

Memory is $O(n)$.

This is easily within the limits in C++.