Problem 219: Skew-cost Coding

Project Euler Problem 219 Solution

EulerSolve provides an optimized solution for Project Euler Problem 219, Skew-cost Coding, with C++, Python, Java, and a step-by-step mathematical explanation.

Problem Summary We want a binary prefix code for $10^9$ symbols. One branch adds cost $1$ and the other adds cost $4$, so the cost of a codeword is the sum of the edge costs along its root-to-leaf path. If $\text{Cost}(n)$ denotes the minimum possible total cost of all codewords for $n$ symbols, then Problem 219 asks for $\text{Cost}(10^9)$. A direct greedy simulation with an explicit priority queue works for tiny values of $n$, but not for $n=10^9$. The implementations therefore replace the evolving leaf set by a counting argument on how many nodes exist at each possible cost. Mathematical Approach The right model is an infinite binary tree rooted at cost $0$. From any node of cost $c$, its two children have costs $c+1$ and $c+4$. A finite prefix-free code is obtained by choosing a finite full subtree and taking its leaves as the codewords. Full Binary Trees and Internal Costs In an optimal code tree, every internal node has exactly two children. A node with only one child would add positive cost without helping the prefix condition, so it can be contracted away. Therefore a code with $n$ leaves has exactly $n-1$ internal nodes. Now start from a single leaf of cost $0$ and expand leaves until $n$ leaves exist. Expanding a leaf of cost $c$ removes that leaf and creates two new leaves of costs $c+1$ and $c+4$....

Detailed mathematical approach

Problem Summary

A bit string is a finite sequence of the bits $\mathtt0$ and $\mathtt1$, and a string $A$ is a prefix of a string $B$ when the leftmost bits of $B$, as many as $A$ has, are exactly $A$. A prefix-free code of size $n$ consists of $n$ distinct bit strings none of which is a prefix of another. Transmitting a $\mathtt0$ costs one penny and a $\mathtt1$ four pence, so a codeword with $z$ zeros and $u$ ones costs $z+4u$ pence. The cost of a code is the total cost of its words, and $\operatorname{Cost}(n)$ is the smallest cost of a prefix-free code of size $n$. The statement shows the code $\mathtt{0000}$, $\mathtt{0001}$, $\mathtt{001}$, $\mathtt{01}$, $\mathtt{10}$, $\mathtt{11}$, whose words cost $4,7,6,5,5,8$ pence, $35$ in all, the cheapest possible: $\operatorname{Cost}(6)=35$. We must find $\operatorname{Cost}(10^9)$. ^[1]

The whole solution in one sentence: starting from the empty word and repeatedly replacing a cheapest word $w$ by $w\mathtt0$ and $w\mathtt1$ gives a cheapest code, so $\operatorname{Cost}(n)$ is $5(n-1)$ plus the total cost of the $n-1$ cheapest bit strings, and these are added a whole cost level at a time, because the strings of each cost can be counted by a simple recurrence.

Mathematical Approach

We picture codes as trees, prove that the internal nodes of a cheapest tree are the cheapest bit strings, and count the strings of each cost, so that a sum of $10^9-1$ terms becomes one over a few dozen levels.

1. Bit strings as an infinite tree

All bit strings form an infinite tree: its root is the empty string $\varepsilon$, and every string $w$ has two children, $w\mathtt0$, reached by an edge of cost $1$, and $w\mathtt1$, reached by an edge of cost $4$. The cost $c(w)$ of a string, its number of zeros plus four times its number of ones, is then the total cost of the edges on the path from the root to $w$. A string is a prefix of another exactly when it lies on the path from the root to the other, so a prefix-free code is a set of nodes of which none lies below another; this tree representation is a standard description of prefix-free codes. ^[2] The cheapest nodes are

cost $0$: $\varepsilon$; cost $1$: $\mathtt0$; cost $2$: $\mathtt{00}$; cost $3$: $\mathtt{000}$;
cost $4$: $\mathtt1$ and $\mathtt{0000}$;
cost $5$: $\mathtt{01}$, $\mathtt{10}$ and $\mathtt{00000}$;
cost $6$: $\mathtt{001}$, $\mathtt{010}$, $\mathtt{100}$ and $\mathtt{000000}$.

A child always costs more than its parent, by $1$ or by $4$, so every proper prefix of a string is strictly cheaper than the string itself.

2. The tree of a code, and why a cheapest one is full

Take a prefix-free code with $n\ge2$ words, and call a string internal if it is a proper prefix of some codeword. No codeword is internal, and the root is: the empty string is a prefix of every string, so with two or more words it is not a codeword. The internal strings and the codewords form the tree of the code, whose leaves are the codewords. In the code of the statement the internal nodes are $\varepsilon$, $\mathtt0$, $\mathtt{00}$, $\mathtt{000}$ and $\mathtt1$, each with both of its children in the tree.

Claim. In a cheapest code every internal node has two children. Proof. Suppose that an internal node $u$ has only the child $ub$, where $b$ is a bit, so that every codeword beginning with $u$ begins with $ub$. Delete this $b$ from all these codewords; among themselves they stay distinct and prefix-free. A codeword $x$ that does not begin with $u$ is not a prefix of $u$ either, as $u$ is a proper prefix of a codeword, so neither of $x$ and a shortened word, which begins with $u$, is a prefix of the other. The new code has $n$ words and is cheaper by $1$ or $4$ pence for each shortened word, so the old one was not cheapest. $\square$

Hence the tree of a cheapest code is a full binary tree: every node has two children or none. Every node except the root is the child of exactly one internal node, so $m$ internal nodes and $n$ leaves satisfy $2m=m+n-1$, that is, $m=n-1$. ^[3]

3. The cost of a full tree

Splitting a leaf $w$ means replacing it by its two children $w\mathtt0$ and $w\mathtt1$. If $c(w)=c$, the total cost of the leaves changes by $(c+1)+(c+4)-c=c+5$: the cost of $w$ is now paid twice instead of once, plus $1+4=5$ for the two new edges. Every full tree grows from the lone root by splitting its internal nodes one after another, parents before children, for instance in order of length. Adding up the changes, a code $X$ whose full tree has the internal nodes $I$ costs

$$\begin{aligned}\sum_{w\in X}c(w)&=\sum_{u\in I}\bigl(c(u)+5\bigr)\\&=5(n-1)+\sum_{u\in I}c(u).\end{aligned}$$

For the code of the statement the internal costs are $0,1,2,3,4$, and indeed $5\cdot5+10=35$.

4. Which sets of internal nodes occur

Call a finite set $I$ of strings closed if it contains every prefix of each of its members. The internal nodes of a code form a closed set, as a prefix of a proper prefix of a codeword is again a proper prefix of it. Conversely, let $I$ be closed with $m\ge1$ members, so that $\varepsilon\in I$, and let $X$ consist of the children of members of $I$ that are not in $I$. If $x\in X$ were a proper prefix of $y\in X$, it would be a prefix of the parent of $y$, which lies in $I$, so $x$ would lie in $I$; hence $X$ is prefix-free. Of the $2m$ children, exactly the $m-1$ members of $I$ other than $\varepsilon$ lie in $I$, so $X$ has $m+1$ words. A proper prefix of a word of $X$ is a prefix of its parent and so lies in $I$, and walking down from a member of $I$ we leave the finite set $I$ at a word of $X$; so $I$ is the set of internal nodes of $X$, and the tree of $X$ is full. With Sections 2 and 3 this proves

$$\operatorname{Cost}(n)=5(n-1)+\min_{I}\sum_{u\in I}c(u),$$

where $I$ runs over the closed sets with $n-1$ members.

5. The key claim: take the cheapest strings

Write the costs of all bit strings in increasing order as $s_1\le s_2\le s_3\le\cdots$; by Section 1 the list begins $0,1,2,3,4,4,5,5,5,6$.

Theorem. For every $n\ge2$,

$$\operatorname{Cost}(n)=5(n-1)+s_1+s_2+\cdots+s_{n-1}.$$

Proof. Any $n-1$ distinct strings cost at least $s_1+\cdots+s_{n-1}$ together, so by Section 4 no code is cheaper than the right-hand side. Conversely, let $C=s_{n-1}$, and let $I$ consist of all strings cheaper than $C$ and enough strings of cost $C$ to make $n-1$ members. A proper prefix of a member of $I$ is strictly cheaper (Section 1), hence cheaper than $C$ and in $I$. So $I$ is closed, and its costs are exactly $s_1,\dots,s_{n-1}$. $\square$

The strings of the last level may be chosen freely: for $n=6$ the cost $4$ may come from $\mathtt1$, giving the code of the statement, or from $\mathtt{0000}$, giving $\mathtt{00000}$, $\mathtt{00001}$, $\mathtt{0001}$, $\mathtt{001}$, $\mathtt{01}$, $\mathtt1$ with the costs $5,8,7,6,5,4$, again $35$.

The theorem also shows that splitting the cheapest leaf again and again is optimal: when the cheapest leaf costs $c$, every cheaper string is already internal, for otherwise it would be a leaf or lie below a leaf, which would be cheaper still. For $n\ge3$ the theorem gives $\operatorname{Cost}(n)-\operatorname{Cost}(n-1)$${}=s_{n-1}+5$, the cost of the split string plus $5$, and $\operatorname{Cost}(2),\dots,\operatorname{Cost}(7)$ are $5,11,18,26,35,44$. With equally likely words, coding with unequal letter costs is the Varn coding problem, solvable in polynomial time; ^[2] for unequal word probabilities no algorithm as efficient as Huffman's is known. ^[4]

6. Counting the strings of each cost

Let $f(c)$ be the number of bit strings of cost $c$. The empty string gives $f(0)=1$, and we set $f(c)=0$ for $c\lt0$. A string of cost $c\ge1$ ends either in $\mathtt0$, and deleting that bit leaves a string of cost $c-1$, or in $\mathtt1$, and deleting it leaves a string of cost $c-4$. In each case deleting the last bit is a one-to-one correspondence, so

$$f(c)=f(c-1)+f(c-4)\qquad(c\ge1).$$

For $c=0,1,\dots,15$ this gives $1,1,1,1,2,3,4,5,$$7,10,14,19,26,36,50,69$, in agreement with Section 1. Reading each $\mathtt0$ as a part $1$ and each $\mathtt1$ as a part $4$, $f(c)$ counts the ways of writing $c$ as an ordered sum of parts $1$ and $4$; it is the sequence A003269 of the OEIS shifted by one place. ^[5] Counting instead by the number $j$ of ones gives a closed formula: such a string has $c-4j$ zeros and length $c-3j$, and its ones may occupy any $j$ of its positions, so

$$f(c)=\sum_{j=0}^{\lfloor c/4\rfloor}\binom{c-3j}{j}.$$

For example $f(8)=\binom80+\binom51+\binom22$${}=7$: the string $\mathtt{00000000}$, the five strings with one $\mathtt1$ and four zeros, and $\mathtt{11}$.

7. Adding a whole cost level at once

Let $A(C)=f(0)+f(1)+\cdots+f(C)$ be the number of strings of cost at most $C$, with $A(-1)=0$. Each cost $c$ appears exactly $f(c)$ times in the list of Section 5. To add its first $m=n-1$ entries, let $C^*$ be the smallest cost with $A(C^*)\ge m$. The levels below $C^*$ are taken completely, and the remaining $m-A(C^*-1)$ entries, at least one and at most $f(C^*)$ of them, all equal $C^*$:

$$\begin{aligned}\sum_{k=1}^{m}s_k&=\sum_{c=0}^{C^*-1}c\,f(c)\\&\quad+C^*\bigl(m-A(C^*-1)\bigr).\end{aligned}$$

The counts $A(C)$ also have a closed form. Writing the recurrence as $f(c)=f(c+4)-f(c+3)$ and adding it for $c=0,1,\dots,C$, the sum telescopes to $A(C)=f(C+4)-f(3)$${}=f(C+4)-1$; for instance $A(4)=6=f(8)-1$.

8. Worked example: $\operatorname{Cost}(20)$

For $n=20$ we need the $m=19$ cheapest strings. The counts $A(0),\dots,A(8)$ are $1,2,3,4,6,9,13,18,25$, so $C^*=8$: the levels $0$ to $7$ supply $18$ strings, and the last one comes from the $f(8)=7$ strings of cost $8$. For $c=0,\dots,7$ the full levels contribute $c\,f(c)=0,1,2,3,8,15,24,35$, together $88$, and the partial level adds $8\cdot(19-18)=8$. Hence

$$\operatorname{Cost}(20)=5\cdot19+88+8=191.$$

In the same way, $C^*=13$ and $\operatorname{Cost}(100)=1455$, and $C^*=20$ and $\operatorname{Cost}(1000)=21708$; the dynamic program of the verification section confirms all three values.

9. Why a few dozen levels suffice

A bit costs between $1$ and $4$, so all $2^L$ strings of length $L=\lfloor C/4\rfloor$ cost at most $C$, and a string of cost at most $C$ has at most $C$ bits. Hence

$$2^{\lfloor C/4\rfloor}\le A(C)\le2^{C+1}-1,$$

so the number of available strings grows exponentially with the cost, and $C^*$ grows only like $\log n$. The exact rate comes from trying $f(c)=x^c$ in the recurrence: dividing by $x^{c-4}$ gives the characteristic equation $x^4=x^3+1$, whose four roots are distinct, and every solution is a combination of their powers. ^[6] The root of largest absolute value is $\rho\approx1.3803$; the other three have absolute values about $0.940$, $0.940$ and $0.819$, so their powers die away: $f(c)$ is in fact the integer nearest to $K\rho^c$, where $K=\rho^4/(\rho^4+3)\approx0.5475$. ^[5] With $A(C)=f(C+4)-1$, $C^*$ differs from $\log_\rho n$ by a bounded amount. For $n=10^9$, where $\log_\rho n\approx64.3$, the loop stops at $C^*=63$, after only $64$ levels, although almost $10^9$ strings are summed.

How the Code Works

The C++ program ^[7] reads the options --n= (default $10^9$), --checkpoint-max-n= (default $200000$) and --skip-checkpoints in parse_arguments. solve_cost(n) returns $0$ for $n\le1$ and otherwise $5(n-1)$ plus sum_smallest_internal_node_costs(n - 1), the theorem of Section 5. That function is the loop of Section 7: its vector multiplicity starts with $f(0)=1$ and gains $f(c)$ from the recurrence of Section 6 when the loop reaches the cost $c$. At each cost the loop takes the smaller of $f(c)$ and the number remaining of strings still missing, adds $c$ times this number to sum and the number itself to used, and stops when used reaches $n-1$.

Unless the checks are skipped, run_checkpoints first requires solve_cost(6) to be $35$. It compares build_cost_multiplicity(70), filled by the recurrence, with cost_multiplicity_combinatorial(c), the binomial sum of Section 6, for every $c\le70$; choose_exact divides after every multiplication, which is exact because each intermediate value is a binomial coefficient. Then greedy_reference_costs(M), where $M$ is the larger of $6$ and the --checkpoint-max-n= value, simulates the splitting of Section 5 with a priority queue of leaf costs: it repeatedly removes the cheapest cost $c$, adds $c+5$ to a running total and inserts $c+1$ and $c+4$, recording $\operatorname{Cost}(n)$ for every $n\le M$. The recorded value at $n=6$ must be $35$, and solve_cost(n) must match every recorded value. Finally main prints the result with to_string_u128.

The C++ code keeps $n$ and the counters in 64-bit integers and the level sizes and sums in the 128-bit extension type __uint128_t (alias u128). ^[8] The Python and Java programs fix $n=10^9$, have no options or checks, and run the same loop over a table of $200$ entries that would grow by $100$ if needed: Python's solve with unbounded integers, Java's main with BigInteger entries, long counters and an int cost index. Java converts a level size with longValueExact only when it is below the number still missing, so the conversion cannot fail. ^[9] The wide types are only a safety margin: at $n=10^9$ every level read has fewer than $4\cdot10^8$ strings, and as no internal cost exceeds $63$, the result is at most $68(n-1)$, well within 64 bits. The Python header comment swaps the two prices; exchanging $\mathtt0$ and $\mathtt1$ in every word shows that this is harmless.

Complexity and Verification

Counting an operation on the stored integers as one step, the main loop does a fixed amount of work at each of the $C^*+1$ levels, so by Section 9 time and memory are $O(\log n)$: for $n=10^9$, $64$ iterations and $64$ table entries (the C++ vector reserves room for $128$; Python and Java allocate $200$). Simulating the splitting directly would take $n-1$ priority-queue steps of $O(\log n)$ each and a queue of $n$ leaves; only the C++ self-check does so, for $n\le M$, in $O(M\log M)$ time before the main computation. On an Apple M4 Max laptop each program finishes within three hundredths of a second, including start-up and the C++ checks.

Besides the C++ checks, we verified the following, which is not part of the published solutions. By Section 2, a cheapest code with $n\ge2$ words has $k\ge1$ words beginning with $\mathtt0$ and $n-k\ge1$ beginning with $\mathtt1$; deleting the first bit leaves two codes, which must be cheapest for their sizes, and removes bits costing $k+4(n-k)=4n-3k$. This gives a dynamic program that does not use Sections 3 to 5: with $T(1)=0$,

$$T(n)=\min_{1\le k\lt n}\bigl(T(k)+T(n-k)+4n-3k\bigr).$$

$T(n)$ agrees with the theorem of Section 5 for every $n\le2000$.
The recurrence equals the binomial sum for $c\le200$, $A(C)=f(C+4)-1$ holds for $C\lt190$, and the bounds and the rounding formula of Section 9 hold for $C,c\lt300$.
The three programs print the same value.

Footnotes and References

The references supply background facts; the reduction to the cheapest internal nodes, the level sums, the examples and the counts are derived in this article.

Project Euler 219 — Skew-cost Coding. The official statement defines prefix-free codes of size n, charges one penny for a 0 bit and four pence for a 1 bit, gives Cost(6) = 35 with a cheapest code and asks for Cost(10⁹).
M. Golin, C. Mathieu and N. E. Young — Huffman Coding with Letter Costs: A Linear-Time Approximation Scheme, SIAM Journal on Computing 41(3), 2012. The paper calls the tree representation a standard representation of prefix-free codes and notes that, with equal word probabilities, coding with letter costs is the Varn coding problem (B. Varn, 1971), solvable in polynomial time.
Wikipedia — Binary tree. In a full binary tree every node has either 0 or 2 children, and a non-empty binary tree with l leaves and i₂ nodes of degree 2 satisfies l = i₂ + 1.
Wikipedia — Huffman coding. With unequal letter costs, as for the dot and dash of Morse code, no algorithm is known that solves the problem with the efficiency of conventional Huffman coding.
OEIS A003269. a(n) = a(n − 1) + a(n − 4) with a(0) = 0 and a(1) = a(2) = a(3) = 1, so f(c) = a(c + 1) is the number of compositions of c into parts 1 and 4. The entry states a(n) = floor(ρ^(n+3)/(ρ⁴ + 3) + 1/2), where ρ = 1.3802775690… is the positive real root of x⁴ − x³ − 1.
Wikipedia — Linear recurrence with constant coefficients. If the roots of the characteristic polynomial are distinct, every solution is a linear combination of their powers, with coefficients fixed by the initial values.
C++ — Euler219.cpp. The linked immutable revision contains sum_smallest_internal_node_costs, solve_cost, greedy_reference_costs and run_checkpoints; it is the implementation record for this article.
GCC manual — 128-bit Integers. GCC provides __int128 and unsigned __int128 on targets with an integer mode wide enough to hold 128 bits.
Python — numeric types: integers have unlimited precision. Java — BigInteger: immutable arbitrary-precision integers; longValueExact throws an ArithmeticException if the value does not fit in a long.

Problem 219 source code

C++

#include <algorithm>
#include <atomic>
#include <cstdint>
#include <exception>
#include <iostream>
#include <limits>
#include <queue>
#include <string>
#include <thread>
#include <vector>

namespace {

using u64 = std::uint64_t;
using u128 = __uint128_t;

struct Options {
    u64 n = 1'000'000'000ULL;
    u64 checkpoint_max_n = 200'000ULL;
    bool run_checkpoints = true;
    unsigned requested_threads = 0U;
};

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

    const std::string tail = arg.substr(prefix.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 std::string& 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 (parse_u64_after_prefix(arg, "--n=", options.n)) {
            continue;
        }
        if (parse_u64_after_prefix(arg, "--checkpoint-max-n=", options.checkpoint_max_n)) {
            continue;
        }
        if (parse_unsigned_after_prefix(arg, "--threads=", options.requested_threads)) {
            continue;
        }

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

    if (options.n == 0ULL) {
        std::cerr << "--n must be >= 1.\n";
        return false;
    }

    return true;
}

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

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

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

u128 choose_exact(unsigned n, unsigned k) {
    if (k > n) {
        return 0U;
    }
    k = std::min(k, n - k);

    u128 result = 1U;
    for (unsigned i = 1; i <= k; ++i) {
        result = (result * static_cast<u128>(n - k + i)) / static_cast<u128>(i);
    }

    return result;
}

std::vector<u128> build_cost_multiplicity(const unsigned max_cost) {
    std::vector<u128> count(static_cast<std::size_t>(max_cost) + 1ULL, 0U);
    count[0] = 1U;

    for (unsigned c = 1; c <= max_cost; ++c) {
        count[c] = count[c - 1];
        if (c >= 4U) {
            count[c] += count[c - 4U];
        }
    }

    return count;
}

u128 cost_multiplicity_combinatorial(const unsigned cost) {
    u128 total = 0U;

    for (unsigned ones = 0; 4U * ones <= cost; ++ones) {
        const unsigned zeros = cost - 4U * ones;
        const unsigned length = zeros + ones;
        total += choose_exact(length, ones);
    }

    return total;
}

u128 sum_smallest_internal_node_costs(const u64 internal_nodes) {
    if (internal_nodes == 0ULL) {
        return 0U;
    }

    std::vector<u128> multiplicity;
    multiplicity.reserve(128U);
    multiplicity.push_back(1U);

    u64 used = 0ULL;
    u128 sum = 0U;

    for (u64 cost = 0ULL; used < internal_nodes; ++cost) {
        if (cost >= multiplicity.size()) {
            u128 next = multiplicity[static_cast<std::size_t>(cost - 1ULL)];
            if (cost >= 4ULL) {
                next += multiplicity[static_cast<std::size_t>(cost - 4ULL)];
            }
            multiplicity.push_back(next);
        }

        const u64 remaining = internal_nodes - used;
        const u64 take = (multiplicity[static_cast<std::size_t>(cost)] >= static_cast<u128>(remaining))
                             ? remaining
                             : static_cast<u64>(multiplicity[static_cast<std::size_t>(cost)]);

        sum += static_cast<u128>(take) * static_cast<u128>(cost);
        used += take;
    }

    return sum;
}

u128 solve_cost(const u64 n) {
    if (n <= 1ULL) {
        return 0U;
    }

    const u64 internal_nodes = n - 1ULL;
    const u128 internal_sum = sum_smallest_internal_node_costs(internal_nodes);
    return static_cast<u128>(5ULL) * static_cast<u128>(internal_nodes) + internal_sum;
}

std::vector<u128> greedy_reference_costs(const u64 max_n) {
    std::vector<u128> costs(static_cast<std::size_t>(max_n) + 1ULL, 0U);
    if (max_n == 0ULL) {
        return costs;
    }

    std::priority_queue<u64, std::vector<u64>, std::greater<u64>> leaves;
    leaves.push(0ULL);

    costs[1] = 0U;
    u128 total = 0U;

    for (u64 n = 2ULL; n <= max_n; ++n) {
        const u64 c = leaves.top();
        leaves.pop();

        total += static_cast<u128>(c) + static_cast<u128>(5ULL);

        leaves.push(c + 1ULL);
        leaves.push(c + 4ULL);

        costs[static_cast<std::size_t>(n)] = total;
    }

    return costs;
}

unsigned pick_thread_count(const unsigned requested_threads, const u64 workload) {
    if (workload < 20'000ULL) {
        return 1U;
    }

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

    if (threads == 0U) {
        threads = 1U;
    }

    if (threads > workload) {
        threads = static_cast<unsigned>(workload);
    }

    return std::max(1U, threads);
}

bool threaded_formula_vs_greedy_check(const std::vector<u128>& reference,
                                      const unsigned requested_threads) {
    if (reference.size() <= 1U) {
        return true;
    }

    const u64 max_n = static_cast<u64>(reference.size() - 1U);
    const unsigned threads = pick_thread_count(requested_threads, max_n);

    std::atomic<bool> ok(true);
    std::atomic<u64> mismatch_n(0ULL);
    std::vector<std::thread> workers;
    workers.reserve(threads);

    for (unsigned t = 0; t < threads; ++t) {
        workers.emplace_back([&, t]() {
            for (u64 n = 1ULL + static_cast<u64>(t); n <= max_n; n += static_cast<u64>(threads)) {
                if (!ok.load(std::memory_order_relaxed)) {
                    return;
                }

                const u128 got = solve_cost(n);
                if (got != reference[static_cast<std::size_t>(n)]) {
                    ok.store(false, std::memory_order_relaxed);
                    mismatch_n.store(n, std::memory_order_relaxed);
                    return;
                }
            }
        });
    }

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

    if (!ok.load(std::memory_order_relaxed)) {
        const u64 n = mismatch_n.load(std::memory_order_relaxed);
        std::cerr << "Checkpoint failed at n=" << n
                  << ": formula=" << to_string_u128(solve_cost(n))
                  << ", greedy=" << to_string_u128(reference[static_cast<std::size_t>(n)])
                  << '\n';
        return false;
    }

    return true;
}

bool run_checkpoints(const Options& options) {
    if (solve_cost(6ULL) != 35U) {
        std::cerr << "Checkpoint failed: Cost(6) must be 35.\n";
        return false;
    }

    constexpr unsigned kCostRecurrenceCheckLimit = 70U;
    const std::vector<u128> recurrence = build_cost_multiplicity(kCostRecurrenceCheckLimit);
    for (unsigned c = 0; c <= kCostRecurrenceCheckLimit; ++c) {
        const u128 via_recurrence = recurrence[c];
        const u128 via_combinatorics = cost_multiplicity_combinatorial(c);
        if (via_recurrence != via_combinatorics) {
            std::cerr << "Checkpoint failed for cost=" << c
                      << ": recurrence=" << to_string_u128(via_recurrence)
                      << ", combinatorics=" << to_string_u128(via_combinatorics)
                      << '\n';
            return false;
        }
    }

    const u64 max_n = std::max<u64>(6ULL, options.checkpoint_max_n);
    const std::vector<u128> reference = greedy_reference_costs(max_n);

    if (reference[6] != 35U) {
        std::cerr << "Checkpoint failed: greedy Cost(6) mismatch.\n";
        return false;
    }

    if (!threaded_formula_vs_greedy_check(reference, options.requested_threads)) {
        return false;
    }

    return true;
}

}  // namespace

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

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

        const u128 answer = solve_cost(options.n);
        std::cout << "Cost(" << options.n << ") = " << to_string_u128(answer) << '\n';
    } catch (const std::exception& ex) {
        std::cerr << "Error: " << ex.what() << '\n';
        return 1;
    }

    return 0;
}

Python

# Problem 219: Skew-cost Coding
# Minimum cost prefix-free code for 10^9 symbols.
# Costs: 1 for bit '1', 4 for bit '0'.
# Greedy: expand cheapest leaf, adding children at cost c+1 and c+4.
# Formula: Cost(n) = 5*(n-1) + sum of (n-1) smallest internal node costs.
# Internal node costs follow recurrence: multiplicity[c] = multiplicity[c-1] + multiplicity[c-4]

def solve():
    n = 1000000000
    if n <= 1:
        print(0)
        return
    
    internal_nodes = n - 1
    
    # Count how many nodes have each cost level
    # multiplicity[c] = multiplicity[c-1] + multiplicity[c-4], multiplicity[0] = 1
    used = 0
    total_cost = 0
    multiplicity = [0] * 200  # grow as needed
    multiplicity[0] = 1
    
    cost = 0
    while used < internal_nodes:
        if cost >= len(multiplicity):
            multiplicity.extend([0] * 100)
        if cost == 0:
            multiplicity[0] = 1
        else:
            multiplicity[cost] = multiplicity[cost - 1]
            if cost >= 4:
                multiplicity[cost] += multiplicity[cost - 4]
        
        remaining = internal_nodes - used
        take = min(multiplicity[cost], remaining)
        total_cost += take * cost
        used += take
        cost += 1
    
    answer = 5 * internal_nodes + total_cost
    print(answer)

solve()

Java

import java.math.BigInteger;

public class Euler219 {
    public static void main(String[] args) {
        long n = 1000000000L;
        if (n <= 1) {
            System.out.println(0);
            return;
        }
        long internalNodes = n - 1;
        // multiplicity[c] = multiplicity[c-1] + multiplicity[c-4], multiplicity[0] = 1
        long used = 0;
        BigInteger totalCost = BigInteger.ZERO;
        BigInteger[] mult = new BigInteger[200];
        mult[0] = BigInteger.ONE;
        int cost = 0;
        while (used < internalNodes) {
            if (cost >= mult.length) {
                BigInteger[] newMult = new BigInteger[mult.length + 100];
                System.arraycopy(mult, 0, newMult, 0, mult.length);
                mult = newMult;
            }
            if (cost > 0) {
                mult[cost] = mult[cost - 1];
                if (cost >= 4)
                    mult[cost] = mult[cost].add(mult[cost - 4]);
            }
            long remaining = internalNodes - used;
            BigInteger rem = BigInteger.valueOf(remaining);
            long take;
            if (mult[cost].compareTo(rem) >= 0)
                take = remaining;
            else
                take = mult[cost].longValueExact();
            totalCost = totalCost.add(BigInteger.valueOf(take).multiply(BigInteger.valueOf(cost)));
            used += take;
            cost++;
        }
        BigInteger answer = BigInteger.valueOf(5).multiply(BigInteger.valueOf(internalNodes)).add(totalCost);
        System.out.println(answer);
    }
}