Detailed mathematical approach

Problem Summary

For a sheet of size \(w \times h\), a legal move chooses an interior grid point \((i,j)\) with \(1 \le i \lt w\) and \(1 \le j \lt h\), then cuts through that point both vertically and horizontally. The current position therefore breaks into four independent rectangles of sizes \(i \times j\), \((w-i) \times j\), \(i \times (h-j)\), and \((w-i) \times (h-j)\).

The solver tracks two quantities for every rectangle: its Sprague-Grundy value \(g_w(h)\), and the number \(c_w(h)\) of legal cuts whose resulting xor is zero. The target quantity is

\[ D(W,H)=\sum_{w=2}^{W}\sum_{h=2}^{H} c_w(h), \]

with the final computation using \(W=123\) and \(H=1{,}234{,}567\). A direct evaluation would inspect an enormous number of cuts, so the whole solution depends on recognizing that, for fixed width, the height behavior eventually stabilizes.

Mathematical Approach

The computation proceeds width by width. Once every smaller width has been reduced to a short explicit prefix plus a constant tail, the next width can be solved by combining those earlier tails instead of exploring every large height separately.

The four-rectangle recurrence

If a \(w \times h\) sheet is cut at \((i,j)\), the four subrectangles are independent impartial subgames, so the child nimber is

\[ x_{i,j}(h)=g_i(j)\oplus g_{w-i}(j)\oplus g_i(h-j)\oplus g_{w-i}(h-j). \]

Therefore

\[ g_w(h)=\operatorname{mex}\{x_{i,j}(h):1\le i \lt w,\ 1\le j \lt h\}, \]

and the companion count is

\[ c_w(h)=\#\{(i,j):1\le i \lt w,\ 1\le j \lt h,\ x_{i,j}(h)=0\}. \]

The symmetry \(j \leftrightarrow h-j\) is immediate: replacing the top pair of rectangles by the bottom pair does not change the xor. The implementation uses that symmetry to process only half of the horizontal cuts explicitly.

Compressing one width split into a one-dimensional sequence

For fixed width \(w\) and fixed vertical split \(i\), define

\[ a_i(t)=g_i(t)\oplus g_{w-i}(t). \]

Then the four-rectangle xor simplifies to

\[ x_{i,j}(h)=a_i(j)\oplus a_i(h-j). \]

This is the key reduction in the solver. Instead of rebuilding four subrectangles for every cut, it first precomputes the sequences \(a_i(t)\), and then each height \(h\) is handled by pairing the entries at \(j\) and \(h-j\).

One immediate consequence is that if \(h\) is even and \(j=h/2\), then

\[ x_{i,h/2}(h)=a_i(h/2)\oplus a_i(h/2)=0. \]

So every vertical split contributes at least one zero-xor move on the center line whenever the height is even.

A safe bound beyond which the move set stops changing

Assume that for each smaller width \(u \lt w\) there is a threshold \(T_u\) and a constant tail nimber \(g_u^{(\infty)}\) such that

\[ g_u(t)=g_u^{(\infty)} \qquad (t\ge T_u). \]

For a fixed split \(i\), put

\[ \tau_i=\max(T_i,T_{w-i}), \qquad \alpha_i=g_i^{(\infty)}\oplus g_{w-i}^{(\infty)}. \]

Then \(a_i(t)=\alpha_i\) for all \(t\ge \tau_i\). Now suppose \(h\ge 2\tau_i+1\). The two numbers \(j\) and \(h-j\) cannot both be \(\lt \tau_i\), because their sum is \(h\). Hence every cut for this split falls into one of two classes:

\[ x_{i,j}(h)=0 \quad \text{if both } j,h-j \ge \tau_i, \]

or

\[ x_{i,j}(h)=a_i(t)\oplus \alpha_i \quad \text{for a unique boundary value } t \lt \tau_i. \]

So once \(h\) is large enough, the set of reachable nimbers contributed by split \(i\) no longer depends on \(h\). Taking the maximum over all vertical splits gives the safe bound

\[ B_w=\max_{1\le i \lt w}(2\tau_i+1). \]

For every \(h\ge B_w\), the full move set of the \(w \times h\) position is identical, so the Grundy value is constant on that tail. Write the constant as \(g_w^{(\infty)}\). The true first stable height \(T_w\) may be smaller than \(B_w\), but \(B_w\) is the point where the proof becomes unconditional.

Why the zero-xor count becomes linear

For one fixed split \(i\) and one height \(h\ge 2\tau_i+1\), the zero-xor cuts can be counted exactly.

The middle band \(j=\tau_i,\tau_i+1,\dots,h-\tau_i\) has length \(h-2\tau_i+1\), and every cut in that band satisfies \(a_i(j)=a_i(h-j)=\alpha_i\), so it contributes xor \(0\).

Boundary cuts come in symmetric pairs \(j=t\) and \(j=h-t\) with \(1\le t \lt \tau_i\). Such a pair contributes xor \(0\) exactly when \(a_i(t)=\alpha_i\). If we define

\[ z_i=\#\{t:1\le t \lt \tau_i,\ a_i(t)=\alpha_i\}, \]

then the contribution of split \(i\) is

\[ c_{w,i}(h)=h-2\tau_i+1+2z_i. \]

Summing over all \(i=1,2,\dots,w-1\) yields the linear tail formula

\[ c_w(h)=(w-1)h+\beta_w, \]

where

\[ \beta_w=\sum_{i=1}^{w-1}(-2\tau_i+1+2z_i). \]

This identity is the main reason the problem is tractable for a huge height bound: once \(B_w\) is reached, the remaining contribution of width \(w\) is just an arithmetic progression.

Worked example: the \(5 \times 3\) sheet

The small case \(w=5\), \(h=3\) is useful because it already shows the true four-rectangle recurrence. The only horizontal cuts are \(j=1\) and \(j=2\), and those are symmetric. From smaller widths we have

\[ g_1(1)=g_1(2)=0,\qquad g_2(1)=0,\ g_2(2)=1,\qquad g_3(1)=0,\ g_3(2)=1,\qquad g_4(1)=0,\ g_4(2)=1. \]

For the split \(i=1\) (and symmetrically \(i=4\)),

\[ x_{1,1}(3)=g_1(1)\oplus g_4(1)\oplus g_1(2)\oplus g_4(2)=0\oplus 0\oplus 0\oplus 1=1. \]

For the split \(i=2\) (and symmetrically \(i=3\)),

\[ x_{2,1}(3)=g_2(1)\oplus g_3(1)\oplus g_2(2)\oplus g_3(2)=0\oplus 0\oplus 1\oplus 1=0. \]

Because \(j=1\) and \(j=2\) give the same xor, the four cuts with \(i=2\) or \(i=3\) are exactly the zero-xor moves. Hence

\[ c_5(3)=4. \]

The reachable nimbers are \(\{0,1\}\), so

\[ g_5(3)=\operatorname{mex}\{0,1\}=2. \]

This is one of the small configurations checked by the solver before the full target sum is accumulated.

How the Code Works

The C++, Python, and Java implementations all expose the same mathematical pipeline. The C++ implementation performs the dynamic program directly, while the Python and Java front ends invoke that same compiled computation, so the logic below is the shared algorithmic core.

Width-by-width state compression

For each width \(w\), the implementation stores only three pieces of permanent information: a short prefix of explicit Grundy values, the first height \(T_w\) from which the tail is known to be constant, and the tail nimber \(g_w^{(\infty)}\). Any query \(g_w(h)\) is answered by reading the prefix if \(h \lt T_w\), and by returning \(g_w^{(\infty)}\) otherwise.

This is why the memory usage depends on the stabilization lengths rather than on the full target height \(H\).

Explicit prefix evaluation for the next width

When width \(w\) is being solved, the implementation first computes the safe bound \(B_w\). It then builds the auxiliary tables \(a_i(t)=g_i(t)\oplus g_{w-i}(t)\) for all \(1\le i \lt w\) and all heights up to \(B_w\).

For each \(h\le B_w\), it scans all vertical splits \(i\) and only half of the horizontal cuts \(j\), using the symmetry \(j \leftrightarrow h-j\) to mark reachable nimbers and to count zero-xor moves. Disjoint ranges of heights are assigned to worker threads, so a whole width layer is filled in parallel without changing the mathematics.

Tail extraction, verification, and summation

After the explicit prefix has been computed, the implementation constructs the stable move set from the boundary values \(t \lt \tau_i\), recovers \(g_w^{(\infty)}\), and computes the intercept \(\beta_w\) in the linear formula \(c_w(h)=(w-1)h+\beta_w\). It verifies those tail formulas against the last explicitly computed height before trusting them.

The true stabilization point \(T_w\) is then found by scanning backward inside the explicit prefix until the values stop differing from \(g_w^{(\infty)}\). Finally, the answer contribution of width \(w\) is split into two parts: the explicit prefix \(2\le h \lt B_w\), and the arithmetic-series tail

\[ \sum_{h=B_w}^{H} c_w(h) =(w-1)\sum_{h=B_w}^{H} h+\beta_w(H-B_w+1). \]

Before the final \(D(123,1{,}234{,}567)\) run, the implementation also checks a smaller benchmark and the sample count \(c_5(3)=4\).

Complexity Analysis

If every rectangle up to height \(H\) were treated directly, then evaluating one state \(w \times h\) would inspect \((w-1)(h-1)\) cuts, and the total work would behave like \(O(W^2H^2)\). That is far too large for the target height.

With stabilization, width \(w\) is evaluated explicitly only up to \(B_w\). Building its prefix costs \(O(wB_w^2)\) time, because the solver processes all heights up to \(B_w\) and for each of them scans all width splits and roughly half of the horizontal cuts. After that, the entire tail contributes in \(O(1)\) time through the arithmetic-series formula. Permanent memory is \(O\!\left(\sum_{w=1}^{W} T_w\right)\) for the stored prefixes, plus \(O(wB_w)\) temporary workspace while the current width is being solved. Parallel threads reduce wall-clock time, but the crucial mathematical improvement is the replacement of dependence on the full \(H\) by dependence on the much smaller stabilization bounds.

Footnotes and References

1. Project Euler 933: Problem 933 - Paper Cutting
2. Sprague-Grundy theorem: Wikipedia - Sprague-Grundy theorem
3. mex operator: Wikipedia - mex (mathematics)
4. Combinatorial game theory: Wikipedia - Combinatorial game theory
5. Arithmetic progression: Wikipedia - Arithmetic progression