Project Euler Problem 750

Solution

Answer: 160640

The key subtlety is that when two stacks are merged, the order inside the resulting stack is determined by which stack is moved onto which.

If a stack containing $i,\dots,k$ is merged with a stack containing $k+1,\dots,j$, then to obtain the ordered stack $i,i+1,\dots,j$, the left stack must be dragged onto the right stack.

Therefore:

the final stack for interval $[i,j]$ always ends at the original position of card $j$,
and if we split at $k$, the merge cost is the distance between the positions of cards $k$ and $j$.

Let $p(x)$ be the original position of card $x$.

Define

$$dp[i][j]$$

to be the minimum cost to combine cards $i,i+1,\dots,j$ into one ordered stack.

Then:

$dp[i][j]=\min_{i\le k<j}\Big(dp[i][k]+dp[k+1][j]+|p(k)-p(j)|\Big)$

with base case

$$dp[i][i]=0.$$

The permutation is generated by:

$$\text{card at position } n = 3^n \bmod (N+1).$$

For $N=6$, this gives:

$$3,2,6,4,5,1$$

and the DP correctly returns $8$.

For $N=16$, it returns the given value $47$.

Using the same DP for $N=976$ gives:

$$G(976)=160640.$$

Answer: 160640