Detailed mathematical approach

Problem Summary

The cards are labeled \(1,2,\dots,n\). Their initial left-to-right order is generated by

$a_i \equiv 3^i \pmod{n+1},\qquad i=1,2,\dots,n.$

For the target case \(n=976\), this construction is treated as a permutation of the labels. The task is to combine all cards into one valid ordered stack with minimum total movement cost. Once the starting order is fixed, the optimization depends only on where each label appears, so the problem becomes an interval dynamic program on consecutive labels.

Mathematical Approach

Let \(P(k)\) be the position of label \(k\) in the generated order. For every interval of labels \(l \le r\), define \(C(l,r)\) as the minimum cost needed to consolidate exactly the cards with labels \(l,l+1,\dots,r\) into one valid stack. The desired answer is \(C(1,n)\).

Step 1: Generate the permutation and the position map

Starting from \(a_0=1\), each new card label is obtained by multiplying by \(3\) modulo \(n+1\). The implementations record, for every label \(k\), the unique position where \(k\) occurs. This produces the position map

$P:\{1,2,\dots,n\}\to\{1,2,\dots,n\}.$

No closed-form shortcut is required later; every cost is expressed directly in terms of these recorded positions.

Step 2: Reduce the problem to consecutive label intervals

Any valid final stack preserves the numerical order of the labels, so whenever we look at labels \(l,l+1,\dots,r\), they behave as one consecutive block in the final construction. That means a complete strategy can be represented by an ordered binary merge tree whose leaves are \(1,2,\dots,n\) from left to right.

Each internal node of that tree corresponds to some interval \([l,r]\), and its last split occurs at some \(m\) with

$l \le m \lt r,$

so the interval is formed by first solving \([l,m]\) and \([m+1,r]\), then merging those two completed sub-stacks.

Step 3: State definition and base case

For a single label there is nothing to merge, so

$C(l,l)=0.$

For longer intervals, \(C(l,r)\) stores the best possible cost over every legal merge order that produces one stack from the labels \(l,l+1,\dots,r\).

Step 4: Derive the recurrence for the last merge

Assume that the last merge for \([l,r]\) splits at \(m\). Then the left subproblem contributes \(C(l,m)\), the right subproblem contributes \(C(m+1,r)\), and the final merge itself contributes the distance between the exposed card of the left block and the exposed card of the right block.

In this interval model, those exposed labels are \(m\) and \(r\), so the extra cost is

$|P(m)-P(r)|.$

Therefore

$C(l,r)=\min_{l \le m \lt r}\left(C(l,m)+C(m+1,r)+|P(m)-P(r)|\right).$

This is the full optimization rule used by the C++, Python, and Java implementations.

Step 5: The global objective

Once every interval cost is known, the whole problem is solved by

$A(n)=C(1,n).$

Because each state depends only on shorter intervals, the table can be filled in increasing order of interval length.

Worked Example: \(n=6\)

For \(n=6\), we work modulo \(7\) and obtain

$a_1,a_2,\dots,a_6 = 3,2,6,4,5,1.$

So the position map is

$P(1)=6,\quad P(2)=2,\quad P(3)=1,\quad P(4)=4,\quad P(5)=5,\quad P(6)=3.$

Some short intervals are immediate:

$C(1,2)=|6-2|=4,\qquad C(2,3)=|2-1|=1,\qquad C(5,6)=|5-3|=2.$

For a length-three interval,

$C(1,3)=\min\bigl(0+1+|6-1|,\ 4+0+|2-1|\bigr)=\min(6,5)=5.$

Likewise,

$C(4,6)=\min\bigl(0+2+|4-3|,\ 1+0+|5-3|\bigr)=\min(3,3)=3.$

Continuing bottom-up gives

$C(1,6)=\min(9,10,10,9,8)=8.$

Hence the optimal total cost for the six-card test case is \(8\), matching the small checkpoint used by the implementations.

How the Code Works

The C++, Python, and Java implementations first generate the permutation by repeated multiplication by \(3\) modulo \(n+1\). As they do so, they store the position of every label. The C++ and Java versions also verify that the sequence really is a permutation with no duplicate or missing label.

Next, the implementation allocates a two-dimensional table for interval costs. The diagonal is initialized to zero because intervals of length \(1\) need no merge.

The main dynamic program processes interval lengths \(2,3,\dots,n\). For each interval \([l,r]\), it tries every split point \(m\), evaluates

$C(l,m)+C(m+1,r)+|P(m)-P(r)|,$

and keeps the minimum. After all lengths are processed, the entry for \([1,n]\) is printed as the answer.

Complexity Analysis

Building the permutation and the position map takes \(O(n)\) time and \(O(n)\) memory. The dynamic program considers every interval \([l,r]\) and, for each one, every split point \(m\). This gives

$O(n^3)$

time in total and

$O(n^2)$

memory for the interval table.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=750
2. Dynamic programming: Wikipedia — Dynamic programming
3. Matrix chain multiplication, a classic interval-DP pattern: Wikipedia — Matrix chain multiplication
4. Permutation: Wikipedia — Permutation
5. Modular arithmetic: Wikipedia — Modular arithmetic