Detailed mathematical approach

Problem Summary

Start with a unit rectangle. In each of the \(ab\) rounds, Alex partitions the current rectangle into an \(a\times b\) grid; cuts may coincide, so some strips may have zero width or height. Bianca then chooses one cell label that has not been used before, and play continues inside that chosen cell. Alex wants the final area to be as large as possible, Bianca wants it as small as possible, and the common value under optimal play is denoted by \(S(a,b)\).

The C++, Python, and Java implementations do not search a minimax tree explicitly. Instead they use a closed formula for \(S(a,b)\) and then evaluate it numerically for \((a,b)=(5,8)\).

Mathematical Approach

The decisive observation is that the geometry separates cleanly into a horizontal game and a vertical game. Once those one-dimensional subgames are solved, the full rectangle value follows immediately.

Step 1: Split the Area into Horizontal and Vertical Factors

In round \(t\), let the column widths be \(x_1^{(t)},\dots,x_a^{(t)}\) with

$x_1^{(t)}+\cdots+x_a^{(t)}=1,$

and let the row heights be \(y_1^{(t)},\dots,y_b^{(t)}\) with

$y_1^{(t)}+\cdots+y_b^{(t)}=1.$

If Bianca chooses the cell in column \(i_t\) and row \(j_t\), then that round multiplies the remaining area by

$x_{i_t}^{(t)}y_{j_t}^{(t)}.$

After all \(ab\) rounds, the final area is

$\prod_{t=1}^{ab} x_{i_t}^{(t)}y_{j_t}^{(t)}=\left(\prod_{t=1}^{ab} x_{i_t}^{(t)}\right)\left(\prod_{t=1}^{ab} y_{j_t}^{(t)}\right).$

So the two-dimensional game factors into a horizontal contribution times a vertical contribution.

Step 2: Track How Often Each Index Must Appear

View the \(ab\) cell labels as the pairs \((i,j)\) with \(1\le i\le a\) and \(1\le j\le b\). Because the game lasts exactly \(ab\) rounds and Bianca may never reuse a label, every pair is used exactly once by the end.

That fixes the total multiplicities automatically:

$\text{each column index }i\text{ appears exactly }b\text{ times},$

$\text{each row index }j\text{ appears exactly }a\text{ times}.$

Hence the horizontal part is a one-dimensional interval game with \(a\) labels, each required \(b\) times, and the vertical part is the same construction with \(b\) labels, each required \(a\) times.

Step 3: Define the One-Dimensional Subgame

Let

$T_n(r_1,\dots,r_n)$

denote the optimal value of the interval version when label \(i\) still has to be chosen \(r_i\) more times. Write

$R=r_1+\cdots+r_n.$

If Alex splits the current interval into lengths \(x_1,\dots,x_n\) with \(x_i\ge 0\) and \(\sum x_i=1\), then Bianca chooses any label with \(r_i>0\). The continuation value is therefore

$x_i\,T_n(r_1,\dots,r_i-1,\dots,r_n).$

So the minimax recurrence is

$T_n(r_1,\dots,r_n)=\max_{\substack{x_i\ge 0\\x_1+\cdots+x_n=1}}\ \min_{r_i>0} x_i\,T_n(r_1,\dots,r_i-1,\dots,r_n).$

Step 4: Equalize All Active Choices

At an optimal split, every currently available choice must lead to the same value. Otherwise Alex could move a little length away from a larger branch and toward a smaller branch, improving the minimum. Thus for every active \(i\),

$x_i\,T_n(r_1,\dots,r_i-1,\dots,r_n)=\lambda$

for one common constant \(\lambda\). Therefore

$x_i=\frac{\lambda}{T_n(r_1,\dots,r_i-1,\dots,r_n)}.$

Summing over all active labels gives

$1=\lambda \sum_{r_i>0}\frac{1}{T_n(r_1,\dots,r_i-1,\dots,r_n)},$

hence

$T_n(r_1,\dots,r_n)=\lambda=\left(\sum_{r_i>0}\frac{1}{T_n(r_1,\dots,r_i-1,\dots,r_n)}\right)^{-1}.$

Step 5: Solve the Recurrence in Closed Form

The recurrence is solved by

$T_n(r_1,\dots,r_n)=\frac{\prod_{i=1}^{n} r_i!}{R!}.$

Indeed, substituting this expression gives

$\frac{1}{T_n(r_1,\dots,r_i-1,\dots,r_n)}=\frac{(R-1)!}{(r_i-1)!\prod_{k\ne i} r_k!}=\frac{(R-1)!}{\prod_{k=1}^{n} r_k!}\,r_i,$

so

$\sum_{r_i>0}\frac{1}{T_n(r_1,\dots,r_i-1,\dots,r_n)}=\frac{(R-1)!}{\prod_{k=1}^{n} r_k!}\sum_{i=1}^{n} r_i=\frac{R!}{\prod_{k=1}^{n} r_k!},$

whose reciprocal is exactly \(\frac{\prod r_i!}{R!}\). The corresponding optimal split is especially simple:

$x_i=\frac{r_i}{R}.$

So each active strip gets length proportional to the number of times it still must be chosen, while exhausted labels can receive zero width because cuts are allowed to coincide.

Step 6: Recombine the Horizontal and Vertical Games

At the start of the horizontal game, there are \(a\) labels and each must be used \(b\) times, hence

$T_a(b,b,\dots,b)=\frac{(b!)^a}{(ab)!}.$

At the start of the vertical game, there are \(b\) labels and each must be used \(a\) times, hence

$T_b(a,a,\dots,a)=\frac{(a!)^b}{(ab)!}.$

Multiplying the independent factors yields

$\boxed{S(a,b)=\frac{(b!)^a(a!)^b}{((ab)!)^2}.}$

This is exactly the formula used by the implementations.

Worked Example

For \((a,b)=(2,2)\), the one-dimensional value is

$T_2(2,2)=\frac{2!\,2!}{4!}=\frac{1}{6},$

so

$S(2,2)=\left(\frac{1}{6}\right)^2=\frac{1}{36}.$

For \((a,b)=(2,3)\), the two factors are

$T_2(3,3)=\frac{(3!)^2}{6!}=\frac{1}{20},\qquad T_3(2,2,2)=\frac{(2!)^3}{6!}=\frac{1}{90},$

and therefore

$S(2,3)=\frac{1}{20}\cdot\frac{1}{90}=\frac{1}{1800},$

which matches the standard checkpoints.

How the Code Works

The C++, Python, and Java implementations all use the closed formula above instead of traversing the full game tree. They evaluate

$\log_{10} S(a,b)=a\log_{10}(b!)+b\log_{10}(a!)-2\log_{10}((ab)!).$

This avoids constructing enormous factorials directly. In C++ and Python, \(\log_{10}(n!)\) is obtained through the identity \(\log(n!)=\log\Gamma(n+1)\); the Java implementation uses the equivalent sum \(\sum_{k=1}^{n}\log_{10} k\).

After computing \(\log_{10}S\), the implementation writes

$\log_{10}S=e+\theta,\qquad e=\lfloor \log_{10}S\rfloor,\qquad 0\le \theta \lt 1,$

so that

$S=10^{\theta}\times 10^{e}.$

The mantissa \(10^{\theta}\) is then rounded to exactly 10 digits after the decimal point. A final carry check is needed because rounding can turn a mantissa such as \(9.99999999996\) into \(10.0000000000\), which must be renormalized as \(1.0000000000\times 10^{e+1}\). The C++ implementation also verifies the small cases \(S(2,2)\) and \(S(2,3)\) before printing the result for \((5,8)\).

Complexity Analysis

For the fixed Project Euler target input, the computation is effectively \(O(1)\) time and \(O(1)\) memory in all three languages. More generally, the mathematical formula itself has constant size once the needed log-factorials are available. The C++ and Python versions obtain them with a constant number of library calls, while the Java version computes them by summing decimal logarithms up to \(ab\), still using only \(O(1)\) extra space.

Footnotes and References

1. Project Euler, Problem 855: https://projecteuler.net/problem=855
2. Gamma function: Wikipedia — Gamma function
3. Factorial: Wikipedia — Factorial
4. Minimax: Wikipedia — Minimax
5. Multinomial coefficient: Wikipedia — Multinomial coefficients