Open Source · 7 Languages · 900+ Problems

Project Euler Solutions

Complete solutions in C++, Python & Java — with step-by-step mathematical explanations

All Problems

Problem 336: Maximix Arrangements

Project Euler Problem 336 Solution

EulerSolve provides an optimized solution for Project Euler Problem 336, Maximix Arrangements, with C++, Python, Java, and a step-by-step mathematical explanation.

Problem Summary We have a train of $n$ distinct carriages labelled $A,B,C,\dots$. Simon sorts it using only suffix reversals: at stage $i$ (using 0-based indexing, as in the code), he takes the next required letter in sorted order, moves it to the tail if necessary, and then reverses the suffix starting at $i$ so that this letter lands permanently at position $i$. A starting permutation is called maximix if Simon is forced to use the largest possible total number of moves. For Project Euler 336, the task is to list all maximix arrangements for $n=11$, sort them lexicographically, and select the requested rank without hard-coding the answer. Mathematical Approach Let $R_i$ denote the operation “reverse the suffix beginning at index $i$”. Because a reversal is an involution, $R_i^{-1}=R_i$; this observation is what makes it possible to construct all maximix states backwards instead of testing every permutation forwards. Simon's Sorting Procedure Fix a stage $i\in\{0,\dots,n-2\}$. The target symbol is the $i$-th symbol of the sorted word $A_1A_2\cdots A_n$. If that symbol is already at index $i$, Simon does nothing. Otherwise, if it is at an interior position $p\in\{i+1,\dots,n-2\}$, Simon first applies $R_p$ to move it to the tail, and then applies $R_i$ to bring it from the tail back to index $i$....

Detailed mathematical approach

Problem Summary

We have a train of $n$ distinct carriages labelled $A,B,C,\dots$. Simon sorts it using only suffix reversals: at stage $i$ (using 0-based indexing, as in the code), he takes the next required letter in sorted order, moves it to the tail if necessary, and then reverses the suffix starting at $i$ so that this letter lands permanently at position $i$. A starting permutation is called maximix if Simon is forced to use the largest possible total number of moves. For Project Euler 336, the task is to list all maximix arrangements for $n=11$, sort them lexicographically, and select the requested rank without hard-coding the answer.

Mathematical Approach

Let $R_i$ denote the operation “reverse the suffix beginning at index $i$”. Because a reversal is an involution, $R_i^{-1}=R_i$; this observation is what makes it possible to construct all maximix states backwards instead of testing every permutation forwards.

Simon's Sorting Procedure

Fix a stage $i\in\{0,\dots,n-2\}$. The target symbol is the $i$-th symbol of the sorted word $A_1A_2\cdots A_n$. If that symbol is already at index $i$, Simon does nothing. Otherwise, if it is at an interior position $p\in\{i+1,\dots,n-2\}$, Simon first applies $R_p$ to move it to the tail, and then applies $R_i$ to bring it from the tail back to index $i$. If it is already at the tail $n-1$, only the second reversal $R_i$ is needed.

So the move count at stage $i$ is

$m_i=\begin{cases} 0, & \text{if the target is already at } i,\\ 1, & \text{if the target is at } n-1,\\ 2, & \text{if the target is at some } p\in\{i+1,\dots,n-2\}. \end{cases}$

Why the Maximum Is $2n-3$

For stages $i=0,1,\dots,n-3$, Simon can spend at most two moves. At the final nontrivial stage $i=n-2$, only two letters remain, so the target can be either already correct (0 moves) or at the tail (1 move); two moves are impossible there.

Therefore the global maximum is

$M_{\max}(n)=\sum_{i=0}^{n-3}2 + 1 = 2(n-2)+1 = 2n-3.$

A permutation is maximix exactly when every early stage $i\le n-3$ forces the two-move case, and the last stage $i=n-2$ forces the one-move case.

Characterizing Maximix States Stage by Stage

This gives a precise local condition. Just before stage $i\le n-3$, the target letter must lie strictly inside the active suffix, not at its left boundary and not at its right boundary. In other words, its position must belong to $\{i+1,\dots,n-2\}$. For the last stage, the smaller of the final two remaining letters must be sitting at position $n-1$, so that a last reversal $R_{n-2}$ is still required.

That description is much stronger than “takes many moves”: it tells us exactly which predecessors are allowed at each stage, which is why a constructive enumeration becomes possible.

Inverse Generation Instead of Forward Brute Force

Let $w^\star = A_1A_2\cdots A_n$ be the fully sorted word. Any maximix arrangement must end at $w^\star$ after Simon finishes. Since each reversal is its own inverse, we can reconstruct all valid predecessors.

The final stage is forced: to need one move at $i=n-2$, the state immediately before the last move must be

$w_{n-2}=R_{n-2}(w^\star).$

Now suppose we already know an after-state for stage $i$, with positions $0,\dots,i$ fixed correctly. In the forward direction, a two-move stage must have been $R_p$ followed by $R_i$, where $p\in\{i+1,\dots,n-2\}$. Reversing that step gives

$\text{before}=R_p\bigl(R_i(\text{after})\bigr),\qquad p=i+1,\dots,n-2.$

Each admissible $p$ yields one branch, and no value $p=n-1$ is allowed, because that would correspond to the one-move case rather than the required two-move case.

Counting by a Bijection

At stage $i$, there are exactly $n-i-2$ admissible choices for $p$. Hence the total number of choice sequences is

$\prod_{i=0}^{n-3}(n-i-2)=(n-2)!.$

This is not merely an upper bound. Simon's forward run determines the actual position $p$ uniquely at each stage, so every maximix arrangement corresponds to exactly one branch sequence $(p_0,p_1,\dots,p_{n-3})$, and every such sequence reconstructs exactly one maximix arrangement. Therefore

$|\mathcal{M}_n|=(n-2)!.$

For $n=11$, this means there are $9! = 362{,}880$ maximix arrangements, which is small enough to generate explicitly.

Worked Example: $n=4$

The sorted word is $ABCD$. First invert the forced last move:

$ABCD \xrightarrow{R_2} ABDC.$

For stage $i=1$, the only possible choice is $p=2$:

$ABDC \xrightarrow{R_1} ACDB \xrightarrow{R_2} ACBD.$

For stage $i=0$, we first apply $R_0$:

$ACBD \xrightarrow{R_0} DBCA.$

Then there are two valid branches:

$DBCA \xrightarrow{R_1} DACB,\qquad DBCA \xrightarrow{R_2} DBAC.$

So the complete maximix set for $n=4$ is $\{DACB, DBAC\}$, and indeed its size is $(4-2)! = 2$. This is the same checkpoint used by the C++ implementation.

How the Code Works

The helper reverse_suffix implements $R_i$. The generator starts from the sorted string ABC..., applies the inverse last move R(n-2), and then iterates $i$ from $n-3$ down to 0. For every current after state it first computes R(i), then branches over all valid $p\in[i+1,n-2]$ by applying R(p). The resulting list of states is exactly the maximix set.

After generation, the states are sorted lexicographically. Because the containers are zero-indexed, the code reads index 2010 to obtain the 2011th maximix arrangement for $n=11$. The C++ version also validates the construction on the known $n=4$ and $n=6$ checkpoints before producing the final ranked string; the Python and Java versions keep the same core generator with less scaffolding.

Complexity Analysis

The generator produces exactly $(n-2)!$ final states. Each branch performs suffix reversals on strings of length $n$, so generation costs $O((n-2)!\cdot n)$. The final lexicographic sort costs $O((n-2)!\log((n-2)!)\cdot n)$ when string-comparison length is taken into account. Memory usage is $O((n-2)!\cdot n)$, since the algorithm stores the full state list. For the fixed input $n=11$, these bounds are entirely practical.