Detailed mathematical approach

Problem Summary

A die is a multiset of six face values chosen from \(\{1,\dots,N\}\); repeated faces are allowed, and the order of faces on a die is irrelevant. For two dice \(X\) and \(Y\), let \(W_{XY}\) denote the number of ordered face pairs \((x,y)\in X\times Y\) with \(x \gt y\). Since there are \(6\cdot 6=36\) comparisons, the statement “\(X\) beats \(Y\) with probability greater than \(1/2\)” is equivalent to \(W_{XY}\ge 19\). The goal is to count unordered triples \(\{A,B,C\}\) such that \(B\) beats \(A\), \(C\) beats \(B\), and \(A\) beats \(C\).

Mathematical Approach

Step 1: Encode each die by multiplicities

For every value \(v\in\{1,\dots,N\}\), write \(a_v,b_v,c_v\) for the number of faces equal to \(v\) on the dice \(A,B,C\). Then

$\sum_{v=1}^{N} a_v=\sum_{v=1}^{N} b_v=\sum_{v=1}^{N} c_v=6,\qquad a_v,b_v,c_v\ge 0.$

This representation is enough because permuting the six faces of a die does not change any pairwise win counts.

Step 2: Sweep the values from \(1\) to \(N\)

The implementation processes face values in increasing order. After finishing value \(v\), define the used-face counts

$u_A=\sum_{t\le v} a_t,\qquad u_B=\sum_{t\le v} b_t,\qquad u_C=\sum_{t\le v} c_t.$

The DP state stores \((u_A,u_B,u_C)\) together with the already determined directed wins \((W_{BA},W_{CB},W_{AC})\). Each win counter is capped at \(19\), because once a counter has reached the threshold, larger values are indistinguishable for the final decision.

Step 3: Derive the transition increments

Suppose the current layer assigns \(a_v=\alpha\), \(b_v=\beta\), \(c_v=\gamma\). A new face of \(B\) with value \(v\) beats exactly the previously placed faces of \(A\), because those are the faces with strictly smaller values. It does not beat equal-value faces placed in the same layer, and larger values have not been processed yet. Therefore the transition adds

$\Delta W_{BA}=\beta\,u_A,\qquad \Delta W_{CB}=\gamma\,u_B,\qquad \Delta W_{AC}=\alpha\,u_C.$

Every winning comparison is counted exactly once: at the moment when the larger of the two face values is inserted.

Step 4: Prune states that can no longer reach the threshold

After updating a state, the code checks a simple optimistic upper bound. If \(B\) still has \(6-u_B\) faces left, then even in the best case those remaining faces can contribute at most \(6(6-u_B)\) further wins against \(A\). Hence a necessary condition is

$W_{BA}+6(6-u_B)\ge 19.$

By the same reasoning, the other two conditions are

$W_{CB}+6(6-u_C)\ge 19,\qquad W_{AC}+6(6-u_A)\ge 19.$

Any state violating one of these bounds is discarded immediately. On the last value, only states with \(u_A=u_B=u_C=6\) are legal.

Step 5: Convert ordered cycles into unordered sets

The DP counts labeled triples satisfying the fixed cyclic orientation

$B\to A,\qquad C\to B,\qquad A\to C.$

Every valid nontransitive set contains three distinct dice, because a die cannot strictly beat itself. For one unordered set, exactly three labelings realize the same oriented cycle: the three cyclic rotations of \((A,B,C)\). The three reversed labelings would require the opposite inequalities and are therefore not counted. Thus

$\text{unordered answer}=\frac{\text{ordered oriented count}}{3}.$

How the Code Works

The C++, Python, and Java solutions all implement this same DP. The C++ version precomputes the transitions for all \(7^3=343\) prefix-count triples, packs each state into a 32-bit integer key, stores counts in unsigned __int128, and can split large layers across multiple threads. The Python version keeps the identical packed state layout inside a dictionary, while the Java version uses dense long[] arrays plus active-key lists for speed. In all three languages, the DP starts from the empty state, iterates through the values \(1,2,\dots,N\), saturates every win counter at \(19\), and finally reads the terminal state

$ (u_A,u_B,u_C,W_{BA},W_{CB},W_{AC})=(6,6,6,19,19,19). $

The C++ implementation also verifies the method with two checkpoints: for \(N=7\) the count is \(9780\), and for \(N=6\) the DP matches a brute-force enumeration over all sorted dice triples.

Complexity Analysis

Because every die has exactly six faces, the compressed state space is bounded by

$7^3\cdot 20^3=2{,}744{,}000,$

since each used-face counter has \(7\) possible values and each saturated win counter has \(20\) possible values. The transition list for a fixed prefix triple is also bounded by a constant. Therefore, for this Project Euler problem, the algorithm is linear in \(N\) with a large but fixed constant, while the memory usage is bounded by the reachable state set and does not grow asymptotically with \(N\). In practice the pruning rules remove most states long before the final layer.

References

1. Problem page: https://projecteuler.net/problem=376
2. Nontransitive dice: Wikipedia — Nontransitive dice
3. Dynamic programming overview: cp-algorithms — Introduction to Dynamic Programming