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 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

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

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());
    }
}