Detailed mathematical approach

Problem Summary

Project Euler 240 asks for the number of ordered outcomes obtained by rolling 20 twelve-sided dice such that, after sorting the 20 results in descending order, the 10 largest values add up to 70. If the sorted roll is \(x_1 \ge x_2 \ge \cdots \ge x_{20}\), the condition is

$x_1+x_2+\cdots+x_{10}=70.$

The dice are distinguishable before sorting, so two rolls with the same multiset of face values still count as different outcomes when those values are assigned to different dice. Any correct method therefore has to count raw rolls, not just sorted patterns.

Mathematical Approach

The implementations solve the problem by scanning face values from 12 down to 1. At each step they decide how many remaining dice show the current face, keep track of how many positions of the top ten have already been forced by larger faces, and accumulate the partial top-ten sum.

Face Multiplicities Encode the Sorted Roll

Let \(c_v\) be the number of dice showing face \(v\), for \(1 \le v \le 12\). Then

$\sum_{v=1}^{12} c_v = 20.$

Once the counts \(c_{12},c_{11},\dots,c_1\) are known, the sorted roll is determined: first come all 12s, then all 11s, and so on. The only subtlety is that not every die contributes to the top-ten sum. If we define \(t_v\) as the number of face-\(v\) dice that actually land in the top ten, then scanning downward gives the deterministic rule

$t_v = \min\!\left(c_v,\ 10-\sum_{w=v+1}^{12} t_w\right).$

The constraint in the problem is therefore equivalent to

$\sum_{v=1}^{12} t_v = 10,\qquad \sum_{v=1}^{12} v\,t_v = 70.$

This is the key invariant behind the dynamic program: when higher faces have already been fixed, the current face can fill only the top-ten slots that are still vacant.

The Right State Space

For \(v=12,11,\dots,1\), let \(D_v(r,m,s)\) denote the number of partial assignments after all faces strictly larger than \(v\) have already been processed, where:

\(r\) is the number of dice whose values have not yet been assigned, \(m\) is the number of positions among the 10 largest dice that are already forced by the larger faces, and \(s\) is the sum contributed by those already forced top-ten entries.

Before any face has been processed, every die is still free and nothing has entered the top ten, so the initial state is

$D_{12}(20,0,0)=1.$

All other initial states are zero.

Transition for One Face Value

Suppose we are processing face \(v\) from a state \((r,m,s)\). Choose \(c\) of the \(r\) remaining dice to show value \(v\). There are

$\binom{r}{c}$

ways to choose which labeled dice receive that value.

Among those \(c\) dice, only

$a=\min(c,10-m)$

can still belong to the top ten, because exactly \(10-m\) top-ten positions remain unfilled and every later face is smaller than \(v\). Therefore the recurrence is

$D_{v-1}(r-c,\ m+a,\ s+a\,v)\;{+}{=}\;D_v(r,m,s)\binom{r}{c},$

provided that \(s+a\,v \le 70\). Once \(m=10\), the top ten are already completely determined, so all lower faces affect only the bottom ten dice and leave the sum unchanged.

Why the Binomial Factors Count Raw Rolls Correctly

If a complete roll has multiplicities \(c_{12},c_{11},\dots,c_1\), then the descending-face sweep contributes the product

$\binom{20}{c_{12}}\binom{20-c_{12}}{c_{11}}\binom{20-c_{12}-c_{11}}{c_{10}}\cdots\binom{c_1}{c_1}.$

This telescopes to

$\frac{20!}{c_{12}!c_{11}!\cdots c_1!},$

which is exactly the multinomial count of how many ordered raw rolls realize that multiset of faces. So the dynamic program is not merely counting sorted histograms; it is counting the actual dice outcomes required by the problem.

Worked Example

The sample configuration in the statement uses 5 six-sided dice and asks for the number of rolls whose largest 3 dice sum to 15; that total is 1111. One local transition explains the recurrence clearly.

Assume faces 6 and 5 have already contributed one die each. Then the state is \((r,m,s)=(3,2,11)\): three dice remain unassigned, two of the top three places are fixed, and their partial sum is 11. If we now assign \(c=2\) dice to face 4, then

$a=\min(2,3-2)=1.$

Only one of those two 4s can still enter the top three, because only one slot is open. The transition factor is \(\binom{3}{2}=3\), and the new state becomes \((1,3,15)\). If the last die later receives value 1, the completed multiset is \((6,5,4,4,1)\), whose number of ordered realizations is

$\binom{5}{1}\binom{4}{1}\binom{3}{2}\binom{1}{1}=60=\frac{5!}{2!}.$

This is exactly the number of raw rolls with that multiset, and only one of the two 4s contributes to the top-three sum.

Final Extraction

After face 1 has been processed, a valid complete roll must have no unassigned dice left, all 10 top positions determined, and top-ten sum 70. Therefore the final answer is

$D_0(0,10,70).$

No other terminal state can represent a complete solution to the original problem.

How the Code Works

Precomputing Combination Counts

The C++, Python, and Java implementations first build Pascal's triangle up to row 20. That provides every binomial coefficient \(\binom{r}{c}\) needed by the recurrence, and it also keeps the main loop free of repeated combinatorial recomputation.

Layer-by-Layer Dynamic Programming

The implementation stores a three-dimensional table indexed by remaining dice, filled top-ten positions, and current top-ten sum. For each face value from 12 down to 1, it creates the next layer, scans every reachable state, and tries every possible number of dice assigned to that face from 0 up to the number still unassigned.

The update uses exactly the recurrence above: compute how many of the newly assigned dice still enter the top ten, update the filled-count and partial sum, multiply by the correct binomial factor, and accumulate into the next layer. States with zero count are skipped immediately.

Reading the Result

After the sweep finishes, the desired count is the entry with 0 dice remaining, 10 top slots filled, and sum 70. The C++ implementation also includes two sanity checks before solving the main instance: it verifies the published sample value 1111 for \((5,6,3,15)\), and it compares one smaller case against a brute-force enumeration. The Python and Java implementations apply the same dynamic program directly to the target parameters.

Complexity Analysis

For general parameters \((N,F,K,S)\), the state space has size \((N+1)(K+1)(S+1)\). For each of the \(F\) face values, each state tries all \(c=0,1,\dots,r\), so the worst-case running time is

$O(F\,N^2KS).$

Using separate current and next layers keeps the memory usage at

$O(NKS).$

For the actual instance \(N=20\), \(F=12\), \(K=10\), \(S=70\), each layer contains only \(21 \cdot 11 \cdot 71 = 16401\) states, so the method is easily fast enough.

Footnotes and References

1. Problem page: Project Euler 240 - Top Dice
2. Dynamic programming: Wikipedia - Dynamic programming
3. Binomial coefficient: Wikipedia - Binomial coefficient
4. Multinomial coefficient: Wikipedia - Multinomial coefficients
5. Order statistic: Wikipedia - Order statistic