Problem 376: Nontransitive Sets of Dice

Project Euler Problem 376 Solution

EulerSolve provides an optimized solution for Project Euler Problem 376, Nontransitive Sets of Dice, with C++, Python, Java, and a step-by-step mathematical explanation.

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})$....

Detailed mathematical approach

Problem Summary

A die here is a multiset of six face values from $\{1,2,\dots,N\}$: repetitions are allowed, the order of the faces is irrelevant, and the same value may appear on several dice of a set. Two players pick dice in turn and roll them; the higher roll wins, and equal rolls are a draw nobody wins. A set of three dice is nontransitive when, whatever die the first player picks, the second can pick one of the other two and win with probability greater than $1/2$. The statement treats $\{A,B,C\}$, $\{B,C,A\}$ and $\{C,A,B\}$ as one set, reports $9780$ such sets for $N=7$ and asks how many there are for $N=30$. ^[1]

Its example is $A=\{1,4,4,4,4,4\}$, $B=\{2,2,2,5,5,5\}$ and $C=\{3,3,3,3,3,6\}$. Here $B$ beats $A$ and $C$ beats $B$ with probability $7/12$, and $A$ beats $C$ with probability $25/36$, so every die is beaten by another one and the second player always has an answer.

The whole solution in one sentence: we sweep the pip values $1,2,\dots,N$ once, carrying only how many faces of each die are already placed and how many of the $36$ comparisons each match-up has won — truncated at the $19$ that settle it — and divide the number of labelled cycles by $3$.

Mathematical Approach

1. How many dice there are

A die is determined by how often each value occurs on it, so the dice are the multisets of size $6$ drawn from $N$ types. Stars and bars counts them — six faces as stars, $N-1$ bars between the value classes: ^[2]

$$D(N)=\binom{N+5}{6}.$$

So $D(7)=924$ and $D(30)=1\,623\,160$. For $N=7$ all $\binom{924}{3}=131\,054\,924$ unordered triples can be inspected, which we do below as a check; for $N=30$ there are $712\,741\,328\,271\,430\,920$ triples, and even the $D(30)^2\approx 2.6\cdot10^{12}$ pairwise comparisons are out of reach. The dice must be counted without being listed.

2. Win counts instead of probabilities

Rolling two dice $X$ and $Y$ picks one of their $6\cdot6=36$ equally likely face pairs. Let $W_{XY}$ count the pairs $(x,y)$ with $x\in X$, $y\in Y$ and $x\gt y$, with multiplicity; the probability that $X$ wins is $W_{XY}/36$, and

$$W_{XY}\gt 18\iff \frac{W_{XY}}{36}\gt\frac12 .$$

Since $W_{XY}$ is an integer, "$X$ beats $Y$" is the purely combinatorial condition $W_{XY}\ge 19$. For the example above, $W_{BA}=21$, $W_{CB}=21$ and $W_{AC}=25$, the fractions $21/36=7/12$ and $25/36$ of the statement.

Draws matter too. With $T_{XY}$ face pairs where $x=y$,

$$W_{XY}+W_{YX}+T_{XY}=36 .$$

Winning more often than losing is not enough to beat an opponent here. Miwin's dice $\{1,2,5,6,7,9\}$, $\{1,3,4,5,8,9\}$ and $\{2,3,4,6,7,8\}$ form a famous cycle in which each die wins $17$ of the $36$ comparisons against the next, loses $16$ and draws $3$. ^[3] Because $17\lt 19$ that set is not counted here, though its faces never exceed $9$, whereas the draw-free set $\{2,2,4,4,9,9\}$, $\{1,1,6,6,8,8\}$, $\{3,3,5,5,7,7\}$, with $W=20$ in each match-up, a probability of $5/9$, is counted from $N=9$ on.

3. Nontransitive means a cycle

Draw an arrow $X\to Y$ whenever $W_{XY}\ge 19$. No pair carries arrows both ways, since $W_{XY}\ge 19$ and $W_{YX}\ge 19$ would give $W_{XY}+W_{YX}\ge 38$, against the identity above; and equal dice give $W_{XY}=W_{YX}$, so they are never joined either and the dice of a counted set are distinct.

Now take three dice in which every die is beaten by another of them. Each has at least one incoming arrow, so there are at least three arrows, and at most three, one per pair. So there are exactly three, one for every pair, and each die receives exactly one; lying in two pairs, each die then also sends out exactly one. Following the arrows from any die therefore visits the other two and returns: the three dice form a directed cycle, and conversely a cycle leaves every die beaten. Nontransitivity is thus the cyclic majority of the Condorcet paradox, where two thirds of the voters prefer $A$ to $B$, $B$ to $C$ and $C$ to $A$. ^[4]

4. From sets to labelled triples

Cycles are easier to count than sets, because a cycle fixes which comparison must be won. We count labelled triples $(A,B,C)$ with

$$W_{BA}\ge 19,\quad W_{CB}\ge 19,\quad W_{AC}\ge 19,$$

that is, the orientation of the statement's example. A nontransitive set admits exactly three such labellings, the rotations of its cycle; the other three describe the same set with the opposite orientation and would need $W_{AB}\ge 19$, which Section 3 forbids. So the number of sets is the number of labelled triples divided by $3$, exactly.

5. Building the three dice value by value

Write $a_v,b_v,c_v$ for the number of faces equal to $v$ on $A,B,C$; a labelled triple is exactly a choice of nonnegative integers with

$$\sum_{v=1}^{N}a_v=\sum_{v=1}^{N}b_v=\sum_{v=1}^{N}c_v=6 .$$

Splitting the comparisons by the value of the winning face gives the identity

$$W_{BA}=\sum_{v=1}^{N}b_v\Bigl(\sum_{u\lt v}a_u\Bigr),$$

and likewise for $W_{CB}$ and $W_{AC}$: a face of $B$ showing $v$ beats precisely the smaller faces of $A$. So we build the dice in increasing order of value. With the values $1,\dots,v-1$ distributed and $u_A,u_B,u_C$ faces placed, choosing $a_v=\alpha$, $b_v=\beta$, $c_v=\gamma$ makes the new faces of $B$ beat the $u_A$ earlier faces of $A$, draw with the $\alpha$ new ones and lose to all later ones, so the counters grow by

$$\begin{aligned}\Delta W_{BA}&=\beta u_A,\\ \Delta W_{CB}&=\gamma u_B,\\ \Delta W_{AC}&=\alpha u_C.\end{aligned}$$

Every winning pair is added once, at the step placing its larger face, and draws are never added because $u_A$ counts the faces of $A$ placed before this value.

6. The state of the sweep

The increments need nothing from the past but $u_A,u_B,u_C$, and the final test nothing but the three counters, so a dynamic programme over $v=1,2,\dots,N$ with the state ^[5]

$$(u_A,u_B,u_C,W_{BA},W_{CB},W_{AC})$$

is enough. It starts at the all-zero state with weight $1$ and at each value adds the weight of a state to every state reachable by a choice $0\le\alpha\le6-u_A$, $0\le\beta\le6-u_B$, $0\le\gamma\le6-u_C$, where $(0,0,0)$ leaves the value unused. No binomial factor appears: faces are not labelled, and the multiplicities alone describe the dice. After the value $N$ the weight of $(6,6,6,W_{BA},W_{CB},W_{AC})$ is the number of labelled triples with exactly these counters: a path through the layers is its sequence of choices, so paths and labelled triples correspond one to one.

7. Truncating the counters at 19

A counter left alone could reach $36$, making the state space needlessly large. We only ask whether it reaches $19$, and counters never decrease, so we may store $\min(W,19)$. Truncation commutes with the updates: for $\delta\ge0$,

$$\min\bigl(\min(W,19)+\delta,\;19\bigr)=\min(W+\delta,19),$$

since both sides are $19$ when $W\ge19$ and $\min(W+\delta,19)$ otherwise. A truncated counter therefore behaves exactly like the true one at the threshold, and the answer is the weight of the single terminal state

$$(6,6,6,19,19,19),$$

divided by $3$. Each truncated counter now has the $20$ possible values $0,1,\dots,19$.

8. Discarding hopeless states

Many states can no longer become a cycle and may be dropped at once. Take the stored counter $W_{BA}$: if it is $19$ the comparison is settled, and if it is smaller it is still exact and can only grow through the unplaced faces of $B$, each beating at most the six faces of $A$. Either way a state can still succeed only if

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

and likewise $W_{CB}+6(6-u_C)\ge19$ and $W_{AC}+6(6-u_A)\ge19$. These tests alone do not force full dice — the all-zero state passes all three at every value — so at the last value the sweep keeps only choices that fill every die. Together the two rules leave exactly one state in the final layer, the terminal one, as a run at $N=30$ confirms.

9. A complete worked example

For $N=5$ there are exactly $15$ nontransitive sets; one of them is

$$A=\{1,1,4,4,4,4\},\; B=\{2,2,2,2,5,5\},$$

$$C=\{3,3,3,3,3,3\},$$

with $W_{BA}=20$, $W_{CB}=24$, $W_{AC}=24$, that is probabilities $5/9$, $2/3$ and $2/3$. The sweep walks through it as follows, with the choice $(\alpha,\beta,\gamma)$, the increments and the state after each value.

$v=1$: $(2,0,0)$, increments $0,0,0$, state $(2,0,0,0,0,0)$.
$v=2$: $(0,4,0)$, increment $\Delta W_{BA}=4\cdot2=8$, state $(2,4,0,8,0,0)$.
$v=3$: $(0,0,6)$, increment $\Delta W_{CB}=6\cdot4=24$, truncated to $19$, state $(2,4,6,8,19,0)$.
$v=4$: $(4,0,0)$, increment $\Delta W_{AC}=4\cdot6=24$, truncated to $19$, state $(6,4,6,8,19,19)$.
$v=5$: $(0,2,0)$, increment $\Delta W_{BA}=2\cdot6=12$, so $8+12=20$ truncated to $19$, state $(6,6,6,19,19,19)$.

The path ends in the terminal state, as it must, and shows truncation at work: the true counters $20,24,24$ are forgotten, but the fact that all three passed $19$ is kept. The state $(2,4,6,8,19,0)$ survives the pruning of Section 8, since $8+6\cdot(6-4)=20\ge19$ and $0+6\cdot(6-2)=24\ge19$.

10. How large the state space really is

Each of $u_A,u_B,u_C$ has $7$ values and each truncated counter $20$, so at most

$$7^3\cdot20^3=2\,744\,000$$

states can ever occur, a bound independent of $N$. The reality is far smaller: $W_{BA}\le u_Au_B$, and the pruning removes much of the rest. Leaving the last value's fullness rule aside, the states reachable after the values $1,\dots,8$ number $27$, $335$, $1686$, $4662$, $7361$, $8582$, $8815$ and $8827$, and one further update reproduces that last set exactly. The update does not depend on the value, so every later ordinary layer holds the same $8827$ states and only their weights change: a run with $N\ge9$ carries $8827$ states from value $8$ to value $N-1$ and one state at value $N$.

11. Small values of $N$

Enumerating all $D(N)$ dice with their win matrix gives the number of nontransitive sets for the first ten $N$:

$N=1,2,3,4$: $0$ sets;
$N=5$: $15$; $N=6$: $581$; $N=7$: $9780$;
$N=8$: $103\,786$; $N=9$: $807\,416$;
$N=10$: $4\,995\,047$.

The value for $N=7$ is the statement's checkpoint. The jump from $0$ at $N=4$ to $15$ at $N=5$ has a sharp explanation: over all $84^3=592\,704$ labelled triples of the $84$ dice with values in $\{1,2,3,4\}$, $\min(W_{BA},W_{CB},W_{AC})$ never exceeds $18$. That value is attained by $\{1,1,1,3,3,3\}$, $\{1,1,1,4,4,4\}$ and $\{2,2,2,2,2,2\}$, where each comparison is won with probability exactly $1/2$ — one short of what the problem demands. The statement's own example needs a $6$, so it is one of the $581$ sets of $N=6$.

Afterwards the counts explode, if only because there are about $D(N)^3/6$ triples to choose from. Research on random dice uses a different family — $n$ faces between $1$ and $n$ with face sum $n(n+1)/2$ — and the weaker relation of Section 2. There the eight win-loss patterns of three dice are conjectured to become equally likely, ^[9] and in one such model a chain $A$, $B$, $C$ provably leaves the probability that $A$ beats $C$ at $1/2+o(1)$. ^[10] Cycles are no rarity, then, though neither result predicts our counts.

How the Code Works

The C++ program ^[6] packs a state into $24$ bits with pack_state and unpack_state — three bits for each of used_a, used_b, used_c, five for each truncated counter w_ba, w_cb, w_ac — and keeps a layer as an unordered_map from key to count. kThreshold is the $19$ of Section 2 and kDefaultN is $30$; --n= runs any other $N$ and --skip-checkpoints omits the self-checks.

build_transitions tabulates the choices of Section 5 once: for each of the $7^3=343$ triples $(u_A,u_B,u_C)$, indexed by prefix_index, every $(\alpha,\beta,\gamma)$ that fits on the remaining faces, together with the increments $\beta u_A$, $\gamma u_B$, $\alpha u_C$ — $28^3=21\,952$ entries in all, $343$ of them for the empty prefix. advance_single_state does the work of Sections 5 to 8 for one state: it skips any transition that would leave a die unfilled when no value is left, adds the increments, truncates at kThreshold, applies the pruning tests and accumulates the count under the new key. advance_layer applies it to every state of a layer, count_ordered_cycles_dp drives the layers $v=1,\dots,N$ and reads off the terminal key, and count_nontransitive_sets_dp divides by $3$.

The same file also holds the direct method, for small $N$: generate_all_dice builds the $D(N)$ multisets recursively by never letting a face fall below its predecessor, and brute_force_nontransitive_sets compares every ordered pair face by face, marks the winners in a bit matrix read by bit_test, and applies the statement's definition literally in its triple loop — each die must be beaten by one of the other two. run_checkpoints uses both halves.

The languages differ mainly in arithmetic and storage. C++ accumulates in unsigned __int128, a compiler extension, ^[7] which is comfortable but not necessary at $N=30$. Every partial count is at most the number of triples of partially filled dice, and padding a die of $k\le6$ faces with $6-k$ blanks makes it a multiset of size $6$ over $31$ symbols, so there are $\binom{36}{6}$ partial dice and at most

$$\binom{36}{6}^{3}=7\,389\,715\,749\,529\,817\,088$$

triples, below $2^{63}-1$. Python builds the table and sweeps inside solve, with a dictionary in the same bit layout and unbounded integers; Java splits that work between buildTransitions and solve. Both fix $N=30$ and neither carries the checkpoints. Java keeps a dense long[] of $10\,485\,760$ entries indexed by the packed key, plus an int[] list of the occupied keys, swapping both pairs of arrays after every value and zeroing each entry as it is consumed. The largest possible key is $10\,282\,934$, so the array is just large enough, and the busiest layer holds $8827$ keys of the $2\,000\,000$ reserved. It prints with Long.divideUnsigned and Long.toUnsignedString, ^[8] correct even beyond the signed range, which the count never leaves: the largest value before the last layer needs $51$ bits.

Complexity and Verification

The sweep runs $N$ layers; a state with $u_A,u_B,u_C$ placed faces has $(7-u_A)(7-u_B)(7-u_C)\le343$ transitions, and Section 10 bounds the states per layer, so the run makes $O(N)$ transition steps in $O(1)$ state slots. A count never exceeds the $O(N^{18})$ possible labelled triples, so each needs $O(\log N)$ bits: in fixed-width words, enough at $N=30$ by the bound above, the run is $O(N)$ time and $O(1)$ memory, and with Python's exact integers $O(N\log N)$ bit operations. At $N=30$ the loops examine $11\,994\,803$ candidate transitions, of which $1\,333\,499$ survive the tests. Wall-clock on one machine, best of three runs: C++ $0.035$ s, or $0.042$ s with its checkpoints, Java $0.101$ s, Python $1.36$ s. Java's fixed arrays are the one extravagance, about $175$ MiB against a few hundred kilobytes of live state.

The packaged checks are the two in run_checkpoints: the sweep reproduces the $9780$ of the statement at $N=7$, and at $N=6$ it agrees with the direct enumeration, which applies the definition word for word rather than the cycle characterisation of Section 3.

Verified independently for this article: a fresh enumeration of all $D(N)$ dice with their win matrix reproduces the counts of Section 11 for every $N\le10$, both by counting cycles and, for $N\le7$, by testing the statement's definition on each of the $\binom{D(N)}{3}$ unordered triples — $131\,054\,924$ of them at $N=7$ — which confirms the equivalence of Section 3. An independent reimplementation of the sweep agrees with that table and with all three published programs at $N=30$, and its labelled count was divisible by $3$ for every $N$ tested, as Section 4 predicts. The statement's probabilities came out as $21/36$, $21/36$ and $25/36$, Miwin's cycle as $17$ wins, $16$ losses and $3$ draws, and the draw-free set of Section 2 as $20$ wins each. Every count at $N=30$ stays below $2^{63}$, so the Java arithmetic is exact.

Footnotes and References

The references below supply the background facts used above. The equivalence between nontransitivity and a cycle, the division by $3$, the sweep, the pruning rule and all measured counts are derived explicitly in this article.

Project Euler 376 — Nontransitive Sets of Dice. The official statement introduces the dice 1-4-4-4-4-4, 2-2-2-5-5-5 and 3-3-3-3-3-6 with the win probabilities 7/12, 7/12 and 25/36, and calls a set of three six-sided dice nontransitive when the second player can always answer the first player's choice. Dice with equal pip sets are equal, rotations of a set are the same set, and equal rolls favour nobody. It gives 9780 sets for N = 7 and asks for the number with pips from 1 to 30.
Wikipedia — Stars and bars (combinatorics). The page's second theorem states that the number of multisets of size n from a set of size k equals the number of k-tuples of non-negative integers summing to n, namely C(n + k − 1, k − 1). With n = 6 faces and k = N values this is D(N) = C(N + 5, 6) of Section 1.
Wikipedia — Nontransitive dice. The page defines a nontransitive set of dice, notes the stronger property that every die is beaten by another one, and gives Section 2's two examples: the draw-free set 2-2-4-4-9-9, 1-1-6-6-8-8, 3-3-5-5-7-7, where each die beats the next with probability 5/9, and Miwin's dice 1-2-5-6-7-9, 1-3-4-5-8-9, 2-3-4-6-7-8, where each wins 17 of the 36 comparisons against the next and loses 16.
Wikipedia — Condorcet paradox. With the rankings A > B > C, B > C > A and C > A > B, two of the three voters prefer A to B, two prefer B to C and two prefer C to A, so the majority relation cycles although every individual ranking is transitive.
Wikipedia — Dynamic programming. The article describes dynamic programming as breaking a problem into overlapping sub-problems, each solved once and stored in a table. The sweep of Section 6 is its bottom-up form: the table for one pip value builds the next, after which the older layer is discarded.
C++ — Euler376.cpp. The linked immutable C++ revision contains pack_state, build_transitions, advance_single_state, count_ordered_cycles_dp, brute_force_nontransitive_sets and run_checkpoints, the constant kThreshold, and the options --n= and --skip-checkpoints. It is the implementation record for this article.
GCC manual — 128-bit integers. The page documents __int128 and unsigned __int128 as available on targets with an integer mode wide enough to hold 128 bits. The C++ accumulators use the unsigned form.
Java — class Long. The documentation states that divideUnsigned returns the quotient with both arguments and the result read as unsigned values, and that toUnsignedString renders its argument as an unsigned decimal with no sign character — the arithmetic of the Java port's final division by 3.
Intransitive Dice. B. Conrey, J. Gabbard, K. Grant, A. Liu and K. Morrison, Mathematics Magazine 89 (2016) 133–143. A die is a non-decreasing tuple of n faces between 1 and n with total n(n+1)/2, and A beats B when P(A > B) exceeds P(B > A); equality is a tie. The paper conjectures that ties vanish as n grows and that the eight win-loss patterns of three dice become equally likely, each with probability tending to 1/8.
The probability that a random triple of dice is transitive. D. H. J. Polymath. In the balanced sequences model a die is a sequence of n values in {1, …, n} with sum n(n+1)/2, drawn uniformly, and A beats B when the face pairs won by A outnumber those won by B. Theorem 1.4 states that two such dice tie with probability o(1), and Theorem 1.5 that P(A beats C | A beats B, B beats C) is 1/2 + o(1).

Problem 376 source code

C++

#include <algorithm>
#include <array>
#include <atomic>
#include <cstdint>
#include <iostream>
#include <limits>
#include <string>
#include <thread>
#include <unordered_map>
#include <utility>
#include <vector>

namespace {

using u64 = std::uint64_t;
using u128 = unsigned __int128;

constexpr int kFacesPerDie = 6;
constexpr int kThreshold = 19;  // Represents wins >= 19, i.e. probability > 1/2.
constexpr int kDefaultN = 30;

struct Options {
    int n = kDefaultN;
    bool run_checkpoints = true;
    bool allow_multithreading = true;
    unsigned requested_threads = 0U;
};

struct Transition {
    std::uint8_t new_used_a = 0;
    std::uint8_t new_used_b = 0;
    std::uint8_t new_used_c = 0;
    std::uint8_t add_w_ba = 0;
    std::uint8_t add_w_cb = 0;
    std::uint8_t add_w_ac = 0;
};

using StateKey = std::uint32_t;
using StateMap = std::unordered_map<StateKey, u128>;

bool parse_u64_after_prefix(const std::string& arg, const char* prefix, u64& value) {
    const std::string p(prefix);
    if (arg.rfind(p, 0) != 0U) {
        return false;
    }

    const std::string tail = arg.substr(p.size());
    if (tail.empty()) {
        return false;
    }

    u64 parsed = 0ULL;
    for (const char c : tail) {
        if (c < '0' || c > '9') {
            return false;
        }

        const u64 digit = static_cast<u64>(c - '0');
        if (parsed > (std::numeric_limits<u64>::max() - digit) / 10ULL) {
            return false;
        }

        parsed = parsed * 10ULL + digit;
    }

    value = parsed;
    return true;
}

bool parse_unsigned_after_prefix(const std::string& arg,
                                 const char* prefix,
                                 unsigned& value) {
    u64 parsed = 0ULL;
    if (!parse_u64_after_prefix(arg, prefix, parsed)) {
        return false;
    }
    if (parsed > static_cast<u64>(std::numeric_limits<unsigned>::max())) {
        return false;
    }

    value = static_cast<unsigned>(parsed);
    return true;
}

bool parse_arguments(const int argc, char** argv, Options& options) {
    for (int i = 1; i < argc; ++i) {
        const std::string arg(argv[i]);

        if (arg == "--skip-checkpoints") {
            options.run_checkpoints = false;
            continue;
        }
        if (arg == "--single-thread") {
            options.allow_multithreading = false;
            continue;
        }

        unsigned parsed_unsigned = 0U;
        if (parse_unsigned_after_prefix(arg, "--threads=", parsed_unsigned)) {
            options.requested_threads = parsed_unsigned;
            continue;
        }

        u64 parsed_u64 = 0ULL;
        if (parse_u64_after_prefix(arg, "--n=", parsed_u64)) {
            if (parsed_u64 > static_cast<u64>(std::numeric_limits<int>::max())) {
                std::cerr << "--n is too large for this implementation.\n";
                return false;
            }
            options.n = static_cast<int>(parsed_u64);
            continue;
        }

        std::cerr << "Unknown argument: " << arg << '\n';
        return false;
    }

    return true;
}

unsigned choose_thread_count(const bool allow_multithreading,
                             const unsigned requested_threads,
                             const std::size_t workload_units,
                             const std::size_t min_units_for_parallel) {
    if (!allow_multithreading || workload_units < min_units_for_parallel || workload_units < 2ULL) {
        return 1U;
    }

    unsigned threads = requested_threads;
    if (threads == 0U) {
        threads = std::thread::hardware_concurrency();
        if (threads == 0U) {
            threads = 1U;
        }
    }

    return std::max(1U, std::min<unsigned>(threads, static_cast<unsigned>(workload_units)));
}

std::string to_string_u128(u128 value) {
    if (value == 0) {
        return "0";
    }

    std::string digits;
    while (value > 0) {
        const unsigned digit = static_cast<unsigned>(value % 10);
        digits.push_back(static_cast<char>('0' + digit));
        value /= 10;
    }

    std::reverse(digits.begin(), digits.end());
    return digits;
}

constexpr int prefix_index(const int used_a, const int used_b, const int used_c) {
    return (used_a * 7 + used_b) * 7 + used_c;
}

constexpr StateKey pack_state(const int used_a,
                              const int used_b,
                              const int used_c,
                              const int w_ba,
                              const int w_cb,
                              const int w_ac) {
    return static_cast<StateKey>(used_a | (used_b << 3) | (used_c << 6) |
                                 (w_ba << 9) | (w_cb << 14) | (w_ac << 19));
}

inline void unpack_state(const StateKey key,
                         int& used_a,
                         int& used_b,
                         int& used_c,
                         int& w_ba,
                         int& w_cb,
                         int& w_ac) {
    used_a = key & 7;
    used_b = (key >> 3) & 7;
    used_c = (key >> 6) & 7;
    w_ba = (key >> 9) & 31;
    w_cb = (key >> 14) & 31;
    w_ac = (key >> 19) & 31;
}

std::vector<std::vector<Transition>> build_transitions() {
    std::vector<std::vector<Transition>> transitions(343);

    for (int used_a = 0; used_a <= kFacesPerDie; ++used_a) {
        for (int used_b = 0; used_b <= kFacesPerDie; ++used_b) {
            for (int used_c = 0; used_c <= kFacesPerDie; ++used_c) {
                auto& list = transitions[static_cast<std::size_t>(prefix_index(used_a, used_b, used_c))];

                const int rem_a = kFacesPerDie - used_a;
                const int rem_b = kFacesPerDie - used_b;
                const int rem_c = kFacesPerDie - used_c;

                for (int add_a = 0; add_a <= rem_a; ++add_a) {
                    const int new_used_a = used_a + add_a;
                    for (int add_b = 0; add_b <= rem_b; ++add_b) {
                        const int new_used_b = used_b + add_b;
                        for (int add_c = 0; add_c <= rem_c; ++add_c) {
                            const int new_used_c = used_c + add_c;

                            Transition tr;
                            tr.new_used_a = static_cast<std::uint8_t>(new_used_a);
                            tr.new_used_b = static_cast<std::uint8_t>(new_used_b);
                            tr.new_used_c = static_cast<std::uint8_t>(new_used_c);
                            tr.add_w_ba = static_cast<std::uint8_t>(add_b * used_a);
                            tr.add_w_cb = static_cast<std::uint8_t>(add_c * used_b);
                            tr.add_w_ac = static_cast<std::uint8_t>(add_a * used_c);
                            list.push_back(tr);
                        }
                    }
                }
            }
        }
    }

    return transitions;
}

inline void advance_single_state(const StateKey key,
                                 const u128 ways,
                                 const int values_left_after,
                                 const std::vector<std::vector<Transition>>& transitions,
                                 StateMap& out) {
    int used_a = 0;
    int used_b = 0;
    int used_c = 0;
    int w_ba = 0;
    int w_cb = 0;
    int w_ac = 0;
    unpack_state(key, used_a, used_b, used_c, w_ba, w_cb, w_ac);

    const auto& list = transitions[static_cast<std::size_t>(prefix_index(used_a, used_b, used_c))];
    for (const Transition& tr : list) {
        if (values_left_after == 0 &&
            (tr.new_used_a != kFacesPerDie || tr.new_used_b != kFacesPerDie || tr.new_used_c != kFacesPerDie)) {
            continue;
        }

        int new_w_ba = w_ba + tr.add_w_ba;
        int new_w_cb = w_cb + tr.add_w_cb;
        int new_w_ac = w_ac + tr.add_w_ac;

        if (new_w_ba > kThreshold) {
            new_w_ba = kThreshold;
        }
        if (new_w_cb > kThreshold) {
            new_w_cb = kThreshold;
        }
        if (new_w_ac > kThreshold) {
            new_w_ac = kThreshold;
        }

        // Remaining B/C/A faces can add at most 6 wins each for w_ba/w_cb/w_ac respectively.
        if (new_w_ba + (kFacesPerDie - tr.new_used_b) * kFacesPerDie < kThreshold) {
            continue;
        }
        if (new_w_cb + (kFacesPerDie - tr.new_used_c) * kFacesPerDie < kThreshold) {
            continue;
        }
        if (new_w_ac + (kFacesPerDie - tr.new_used_a) * kFacesPerDie < kThreshold) {
            continue;
        }

        const StateKey next_key =
            pack_state(tr.new_used_a, tr.new_used_b, tr.new_used_c, new_w_ba, new_w_cb, new_w_ac);
        out[next_key] += ways;
    }
}

void advance_layer(const StateMap& current,
                   const int values_left_after,
                   const std::vector<std::vector<Transition>>& transitions,
                   const bool allow_multithreading,
                   const unsigned requested_threads,
                   StateMap& next) {
    next.clear();

    constexpr std::size_t kMinUnitsForParallel = 35'000ULL;
    const unsigned thread_count = choose_thread_count(
        allow_multithreading, requested_threads, current.size(), kMinUnitsForParallel);

    if (thread_count == 1U) {
        next.reserve(current.size() * 8ULL + 256ULL);
        for (const auto& kv : current) {
            advance_single_state(kv.first, kv.second, values_left_after, transitions, next);
        }
        return;
    }

    std::vector<std::pair<StateKey, u128>> items;
    items.reserve(current.size());
    for (const auto& kv : current) {
        items.push_back(kv);
    }

    std::vector<StateMap> local_maps(thread_count);
    std::vector<std::thread> workers;
    workers.reserve(thread_count);

    const std::size_t block_size = (items.size() + thread_count - 1ULL) / thread_count;
    for (unsigned tid = 0; tid < thread_count; ++tid) {
        workers.emplace_back([&, tid]() {
            const std::size_t begin = static_cast<std::size_t>(tid) * block_size;
            const std::size_t end = std::min(items.size(), begin + block_size);
            if (begin >= end) {
                return;
            }

            StateMap& local = local_maps[tid];
            local.reserve((end - begin) * 8ULL + 64ULL);

            for (std::size_t idx = begin; idx < end; ++idx) {
                advance_single_state(items[idx].first,
                                     items[idx].second,
                                     values_left_after,
                                     transitions,
                                     local);
            }
        });
    }

    for (std::thread& worker : workers) {
        worker.join();
    }

    std::size_t total_size = 0ULL;
    for (const StateMap& local : local_maps) {
        total_size += local.size();
    }
    next.reserve(total_size + 256ULL);

    for (const StateMap& local : local_maps) {
        for (const auto& kv : local) {
            next[kv.first] += kv.second;
        }
    }
}

u128 count_ordered_cycles_dp(const int n,
                             const bool allow_multithreading,
                             const unsigned requested_threads) {
    if (n <= 0) {
        return 0;
    }

    static const std::vector<std::vector<Transition>> transitions = build_transitions();

    StateMap current;
    StateMap next;
    current.reserve(4'096ULL);
    next.reserve(4'096ULL);
    current[pack_state(0, 0, 0, 0, 0, 0)] = 1;

    for (int value = 1; value <= n; ++value) {
        const int values_left_after = n - value;
        advance_layer(current,
                      values_left_after,
                      transitions,
                      allow_multithreading,
                      requested_threads,
                      next);
        current.swap(next);
    }

    const StateKey terminal = pack_state(kFacesPerDie, kFacesPerDie, kFacesPerDie,
                                         kThreshold, kThreshold, kThreshold);
    const auto it = current.find(terminal);
    return (it == current.end()) ? 0 : it->second;
}

u128 count_nontransitive_sets_dp(const int n,
                                 const bool allow_multithreading,
                                 const unsigned requested_threads) {
    const u128 ordered = count_ordered_cycles_dp(n, allow_multithreading, requested_threads);
    return ordered / 3;
}

void generate_dice_rec(const int n,
                       const int depth,
                       const int min_value,
                       std::array<std::uint8_t, kFacesPerDie>& current,
                       std::vector<std::array<std::uint8_t, kFacesPerDie>>& out) {
    if (depth == kFacesPerDie) {
        out.push_back(current);
        return;
    }

    for (int value = min_value; value <= n; ++value) {
        current[static_cast<std::size_t>(depth)] = static_cast<std::uint8_t>(value);
        generate_dice_rec(n, depth + 1, value, current, out);
    }
}

std::vector<std::array<std::uint8_t, kFacesPerDie>> generate_all_dice(const int n) {
    std::vector<std::array<std::uint8_t, kFacesPerDie>> dice;
    std::array<std::uint8_t, kFacesPerDie> current{};
    generate_dice_rec(n, 0, 1, current, dice);
    return dice;
}

inline bool bit_test(const std::vector<u64>& row, const int index) {
    return ((row[static_cast<std::size_t>(index >> 6)] >> (index & 63)) & 1ULL) != 0ULL;
}

u64 brute_force_nontransitive_sets(const int n,
                                   const bool allow_multithreading,
                                   const unsigned requested_threads) {
    if (n <= 0) {
        return 0ULL;
    }

    const std::vector<std::array<std::uint8_t, kFacesPerDie>> dice = generate_all_dice(n);
    const int m = static_cast<int>(dice.size());
    const int word_count = (m + 63) / 64;

    std::vector<std::vector<u64>> wins(static_cast<std::size_t>(m),
                                       std::vector<u64>(static_cast<std::size_t>(word_count), 0ULL));

    const unsigned pair_threads =
        choose_thread_count(allow_multithreading, requested_threads, static_cast<std::size_t>(m), 64ULL);

    {
        std::atomic<int> next_i(0);
        std::vector<std::thread> workers;
        workers.reserve(pair_threads);

        for (unsigned tid = 0; tid < pair_threads; ++tid) {
            workers.emplace_back([&]() {
                while (true) {
                    const int i = next_i.fetch_add(1, std::memory_order_relaxed);
                    if (i >= m) {
                        break;
                    }

                    auto& row = wins[static_cast<std::size_t>(i)];
                    for (int j = 0; j < m; ++j) {
                        if (i == j) {
                            continue;
                        }

                        int win_count = 0;
                        for (const std::uint8_t x : dice[static_cast<std::size_t>(i)]) {
                            for (const std::uint8_t y : dice[static_cast<std::size_t>(j)]) {
                                if (x > y) {
                                    ++win_count;
                                }
                            }
                        }

                        if (win_count >= kThreshold) {
                            row[static_cast<std::size_t>(j >> 6)] |= (1ULL << (j & 63));
                        }
                    }
                }
            });
        }

        for (std::thread& worker : workers) {
            worker.join();
        }
    }

    const unsigned triple_threads =
        choose_thread_count(allow_multithreading, requested_threads, static_cast<std::size_t>(m), 32ULL);
    std::vector<u64> partial(static_cast<std::size_t>(triple_threads), 0ULL);

    {
        std::atomic<int> next_i(0);
        std::vector<std::thread> workers;
        workers.reserve(triple_threads);

        for (unsigned tid = 0; tid < triple_threads; ++tid) {
            workers.emplace_back([&, tid]() {
                u64 local = 0ULL;

                while (true) {
                    const int i = next_i.fetch_add(1, std::memory_order_relaxed);
                    if (i >= m) {
                        break;
                    }

                    for (int j = i + 1; j < m; ++j) {
                        for (int k = j + 1; k < m; ++k) {
                            // For each die, one of the other two must beat it.
                            const bool i_beaten = bit_test(wins[static_cast<std::size_t>(j)], i) ||
                                                  bit_test(wins[static_cast<std::size_t>(k)], i);
                            if (!i_beaten) {
                                continue;
                            }

                            const bool j_beaten = bit_test(wins[static_cast<std::size_t>(i)], j) ||
                                                  bit_test(wins[static_cast<std::size_t>(k)], j);
                            if (!j_beaten) {
                                continue;
                            }

                            const bool k_beaten = bit_test(wins[static_cast<std::size_t>(i)], k) ||
                                                  bit_test(wins[static_cast<std::size_t>(j)], k);
                            if (k_beaten) {
                                ++local;
                            }
                        }
                    }
                }

                partial[static_cast<std::size_t>(tid)] = local;
            });
        }

        for (std::thread& worker : workers) {
            worker.join();
        }
    }

    u64 total = 0ULL;
    for (const u64 count : partial) {
        total += count;
    }
    return total;
}

bool run_checkpoints(const Options& options) {
    const u128 sample = count_nontransitive_sets_dp(7,
                                                    options.allow_multithreading,
                                                    options.requested_threads);
    if (sample != static_cast<u128>(9'780ULL)) {
        std::cerr << "Checkpoint failed for N=7: expected 9780, got "
                  << to_string_u128(sample) << '\n';
        return false;
    }

    const u128 dp_n6 = count_nontransitive_sets_dp(6,
                                                   options.allow_multithreading,
                                                   options.requested_threads);
    const u64 brute_n6 = brute_force_nontransitive_sets(6,
                                                        options.allow_multithreading,
                                                        options.requested_threads);
    if (dp_n6 != static_cast<u128>(brute_n6)) {
        std::cerr << "Checkpoint failed for N=6: DP gives " << to_string_u128(dp_n6)
                  << ", brute force gives " << brute_n6 << '\n';
        return false;
    }

    const unsigned threads = choose_thread_count(options.allow_multithreading,
                                                 options.requested_threads,
                                                 std::size_t{500},
                                                 std::size_t{2});
    std::cout << "Checkpoints passed (threads=" << threads << ").\n";
    return true;
}

}  // namespace

int main(int argc, char** argv) {
    Options options;
    if (!parse_arguments(argc, argv, options)) {
        return 1;
    }

    if (options.run_checkpoints && !run_checkpoints(options)) {
        return 1;
    }

    const u128 answer = count_nontransitive_sets_dp(options.n,
                                                    options.allow_multithreading,
                                                    options.requested_threads);
    std::cout << "Answer: " << to_string_u128(answer) << '\n';
    return 0;
}

Python

def solve():
    transitions = [[] for _ in range(343)]
    for used_a in range(7):
        for used_b in range(7):
            for used_c in range(7):
                idx = (used_a * 7 + used_b) * 7 + used_c
                for add_a in range(7 - used_a):
                    new_a = used_a + add_a
                    for add_b in range(7 - used_b):
                        new_b = used_b + add_b
                        for add_c in range(7 - used_c):
                            transitions[idx].append((
                                new_a, new_b, used_c + add_c,
                                add_b * used_a,
                                add_c * used_b,
                                add_a * used_c
                            ))
                            
    n = 30
    current = {0: 1}
    
    for value in range(1, n + 1):
        next_states = {}
        values_left_after = n - value
        
        for key, ways in current.items():
            used_a = key & 7
            used_b = (key >> 3) & 7
            used_c = (key >> 6) & 7
            w_ba = (key >> 9) & 31
            w_cb = (key >> 14) & 31
            w_ac = (key >> 19) & 31
            
            idx = (used_a * 7 + used_b) * 7 + used_c
            
            for tr in transitions[idx]:
                n_a, n_b, n_c, ad_ba, ad_cb, ad_ac = tr
                
                if values_left_after == 0 and (n_a != 6 or n_b != 6 or n_c != 6):
                    continue
                    
                nw_ba = w_ba + ad_ba
                nw_cb = w_cb + ad_cb
                nw_ac = w_ac + ad_ac
                
                if nw_ba > 19: nw_ba = 19
                if nw_cb > 19: nw_cb = 19
                if nw_ac > 19: nw_ac = 19
                
                if nw_ba + (6 - n_b) * 6 < 19: continue
                if nw_cb + (6 - n_c) * 6 < 19: continue
                if nw_ac + (6 - n_a) * 6 < 19: continue
                
                nkey = n_a | (n_b << 3) | (n_c << 6) | (nw_ba << 9) | (nw_cb << 14) | (nw_ac << 19)
                next_states[nkey] = next_states.get(nkey, 0) + ways
                
        current = next_states
        
    terminal = 6 | (6 << 3) | (6 << 6) | (19 << 9) | (19 << 14) | (19 << 19)
    ans = current.get(terminal, 0) // 3
    return str(ans)

if __name__ == '__main__':
    print(solve())

Java

import java.util.ArrayList;
import java.util.List;

public class Euler376 {

    static class Transition {
        int nA, nB, nC;
        int maxWBa, maxWCb, maxWAc;

        Transition(int nA, int nB, int nC, int adBa, int adCb, int adAc) {
            this.nA = nA;
            this.nB = nB;
            this.nC = nC;
            this.maxWBa = adBa;
            this.maxWCb = adCb;
            this.maxWAc = adAc;
        }
    }

    @SuppressWarnings("unchecked")
    static List<Transition>[] buildTransitions() {
        List<Transition>[] transitions = new ArrayList[343];
        for (int i = 0; i < 343; i++)
            transitions[i] = new ArrayList<>();

        for (int usedA = 0; usedA <= 6; usedA++) {
            for (int usedB = 0; usedB <= 6; usedB++) {
                for (int usedC = 0; usedC <= 6; usedC++) {
                    int idx = (usedA * 7 + usedB) * 7 + usedC;
                    for (int addA = 0; addA <= 6 - usedA; addA++) {
                        for (int addB = 0; addB <= 6 - usedB; addB++) {
                            for (int addC = 0; addC <= 6 - usedC; addC++) {
                                transitions[idx].add(new Transition(
                                        usedA + addA,
                                        usedB + addB,
                                        usedC + addC,
                                        addB * usedA,
                                        addC * usedB,
                                        addA * usedC));
                            }
                        }
                    }
                }
            }
        }
        return transitions;
    }

    static String solve() {
        List<Transition>[] transitions = buildTransitions();
        int n = 30;

        long[] current = new long[10485760];
        int[] currentKeys = new int[2000000];
        int currentSize = 0;

        current[0] = 1;
        currentKeys[currentSize++] = 0;

        long[] next = new long[10485760];
        int[] nextKeys = new int[2000000];

        for (int value = 1; value <= n; value++) {
            int nextSize = 0;
            int valuesLeftAfter = n - value;

            for (int i = 0; i < currentSize; i++) {
                int key = currentKeys[i];
                long ways = current[key];
                current[key] = 0; // Clear for next reuse

                int usedA = key & 7;
                int usedB = (key >> 3) & 7;
                int usedC = (key >> 6) & 7;
                int wBa = (key >> 9) & 31;
                int wCb = (key >> 14) & 31;
                int wAc = (key >> 19) & 31;

                int idx = (usedA * 7 + usedB) * 7 + usedC;
                for (Transition tr : transitions[idx]) {
                    if (valuesLeftAfter == 0 && (tr.nA != 6 || tr.nB != 6 || tr.nC != 6)) {
                        continue;
                    }

                    int nwBa = wBa + tr.maxWBa;
                    int nwCb = wCb + tr.maxWCb;
                    int nwAc = wAc + tr.maxWAc;

                    if (nwBa > 19)
                        nwBa = 19;
                    if (nwCb > 19)
                        nwCb = 19;
                    if (nwAc > 19)
                        nwAc = 19;

                    if (nwBa + (6 - tr.nB) * 6 < 19)
                        continue;
                    if (nwCb + (6 - tr.nC) * 6 < 19)
                        continue;
                    if (nwAc + (6 - tr.nA) * 6 < 19)
                        continue;

                    int nkey = tr.nA | (tr.nB << 3) | (tr.nC << 6) | (nwBa << 9) | (nwCb << 14) | (nwAc << 19);

                    if (next[nkey] == 0) {
                        nextKeys[nextSize++] = nkey;
                    }
                    next[nkey] += ways;
                }
            }

            long[] tempArr = current;
            current = next;
            next = tempArr;

            int[] tempKeys = currentKeys;
            currentKeys = nextKeys;
            nextKeys = tempKeys;

            currentSize = nextSize;
        }

        int terminal = 6 | (6 << 3) | (6 << 6) | (19 << 9) | (19 << 14) | (19 << 19);
        long ways = current[terminal];
        // Uses unsigned division because it might exceed signed max.
        // Long.divideUnsigned works properly.
        long ans = Long.divideUnsigned(ways, 3);

        return Long.toUnsignedString(ans);
    }

    public static void main(String[] args) {
        System.out.println(solve());
    }
}