Problem 259: Reachable Numbers

Mathematical Foundation

Definition. For indices $1 \le i \le j \le 9$, let $R(i,j) \subseteq \mathbb{Q}$ be the set of all rational numbers obtainable from the contiguous digit substring $d_i d_{i+1} \cdots d_j$ (where $d_k = k$) by partitioning, operator insertion, and arbitrary parenthesization.

Lemma 1 (Base Case). $R(i,j)$ always contains the concatenated integer $\overline{d_i d_{i+1} \cdots d_j}$. In particular, $R(i,i) = \{i\}$ is the singleton containing digit $i$.

Proof. The trivial partition (no splits) produces the concatenated number. For a single digit, no operators can be inserted, so the only value is the digit itself. $\square$

Theorem 1 (Interval DP Recurrence). For $j > i$, the set $R(i,j)$ satisfies:

Proof. Any expression over $d_i, \ldots, d_j$ either treats all digits as one concatenated number (no operator at the top level) or has a “last” binary operator $\circ$ applied between some left part $d_i \cdots d_k$ and right part $d_{k+1} \cdots d_j$. The left and right subexpressions can independently be any value in $R(i,k)$ and $R(k+1,j)$ respectively, by induction. The split point $k$ ranges over all valid positions. $\square$

Theorem 2 (Correctness of Interval DP). The recurrence in Theorem 1 produces exactly the set of all obtainable values. That is, every binary expression tree over the ordered leaves $d_i, \ldots, d_j$ (with contiguous groups at the leaves) corresponds to some choice of split point and recursive subexpressions.

Proof. By structural induction on expression trees. A tree with one leaf corresponds to the base case. A tree with root operator $\circ$, left subtree over $d_i \cdots d_k$, and right subtree over $d_{k+1} \cdots d_j$ is captured by the union in the recurrence. Since every expression tree has a unique root split, the correspondence is exhaustive. $\square$

Lemma 2 (Exact Arithmetic). Division may produce non-integer rationals (e.g., $1/2$). Using exact rational arithmetic (representing each value as a fraction $p/q$ in lowest terms) ensures no precision loss.

Proof. All inputs are integers, and closure of $\mathbb{Q}$ under $\{+,-,\times,\div\}$ (excluding division by zero) ensures all intermediate and final values are rational. $\square$

Editorial

From the string “123456789”, insert +, -, *, / between groups of consecutive digits (with arbitrary parenthesization) to produce values. Find the sum of all positive integers reachable. Method: Interval DP with exact rational arithmetic (fractions). R(i,j) = set of all rationals from digits i..j. We digits: d[1]=1, d[2]=2, …, d[9]=9. We then compute R(i,j) for all 1 <= i <= j <= 9 using interval DP. Finally, base case.

Pseudocode

Digits: d[1]=1, d[2]=2, ..., d[9]=9
Compute R(i,j) for all 1 <= i <= j <= 9 using interval DP
Base case
Fill DP table by increasing interval length
Extract positive integers from R[1][9]

Complexity Analysis

• Time: There are $\binom{9}{2} + 9 = 45$ subproblems. Each $|R(i,j)|$ is bounded empirically by a few thousand. For the full interval $R(1,9)$, the set size is at most $\sim 10^5$. The total work is $O\!\left(\sum_{i \le j} (j-i) \cdot |R(i,\cdot)| \cdot |R(\cdot,j)|\right)$, which is bounded and completes in under one second.
• Space: $O\!\left(\sum_{i \le j} |R(i,j)|\right)$, on the order of $10^5$ rational numbers.

Answer

#include <bits/stdc++.h>
using namespace std;

/*
 * Problem 259: Reachable Numbers
 *
 * From the string "123456789", by concatenating adjacent digits and inserting
 * +, -, *, / between groups (with arbitrary parenthesization), find the sum
 * of all positive integers that can be produced.
 *
 * Method: Interval DP over substrings. R(i,j) = set of all rationals
 * achievable from digits i..j. Use exact fractions (p/q in lowest terms).
 *
 * Answer: 20101196798
 */

typedef pair<long long, long long> Frac; // (numerator, denominator), always reduced, denom > 0

long long gcd_abs(long long a, long long b) {
    a = abs(a); b = abs(b);
    while (b) { a %= b; swap(a, b); }
    return a;
}

Frac make_frac(long long p, long long q) {
    if (q == 0) return {0, 0}; // invalid
    if (p == 0) return {0, 1};
    if (q < 0) { p = -p; q = -q; }
    long long g = gcd_abs(p, q);
    return {p / g, q / g};
}

Frac add(Frac a, Frac b) { return make_frac(a.first * b.second + b.first * a.second, a.second * b.second); }
Frac sub(Frac a, Frac b) { return make_frac(a.first * b.second - b.first * a.second, a.second * b.second); }
Frac mul(Frac a, Frac b) { return make_frac(a.first * b.first, a.second * b.second); }
Frac divf(Frac a, Frac b) {
    if (b.first == 0) return {0, 0};
    return make_frac(a.first * b.second, a.second * b.first);
}

set<Frac> dp[10][10]; // dp[i][j] for digits i..j (1-indexed)
bool computed[10][10];

long long concat_num(int i, int j) {
    long long num = 0;
    for (int k = i; k <= j; k++) num = num * 10 + k;
    return num;
}

void solve(int i, int j) {
    if (computed[i][j]) return;
    computed[i][j] = true;

    // Base: concatenated number
    dp[i][j].insert(make_frac(concat_num(i, j), 1));

    // Split
    for (int k = i; k < j; k++) {
        solve(i, k);
        solve(k + 1, j);
        for (auto& a : dp[i][k]) {
            for (auto& b : dp[k+1][j]) {
                dp[i][j].insert(add(a, b));
                dp[i][j].insert(sub(a, b));
                dp[i][j].insert(mul(a, b));
                Frac d = divf(a, b);
                if (d.second != 0) dp[i][j].insert(d);
            }
        }
    }
}

int main() {
    memset(computed, false, sizeof(computed));
    solve(1, 9);

    long long ans = 0;
    for (auto& f : dp[1][9]) {
        if (f.second == 1 && f.first > 0) {
            ans += f.first;
        }
    }
    cout << ans << endl;
    return 0;
}

"""
Problem 259: Reachable Numbers

From the string "123456789", insert +, -, *, / between groups of consecutive
digits (with arbitrary parenthesization) to produce values. Find the sum of
all positive integers reachable.

Method: Interval DP with exact rational arithmetic (fractions).
R(i,j) = set of all rationals from digits i..j.

Answer: 20101196798
"""

from fractions import Fraction
from functools import lru_cache

def solve():
    digits = list(range(1, 10))  # 1..9, 0-indexed as 0..8

    # dp[i][j] = set of Fraction values from digits[i..j]
    dp = [[None] * 9 for _ in range(9)]

    def get(i, j):
        if dp[i][j] is not None:
            return dp[i][j]

        s = set()

        # Concatenated number
        num = 0
        for k in range(i, j + 1):
            num = num * 10 + digits[k]
        s.add(Fraction(num))

        # Split at every point
        for k in range(i, j):
            left = get(i, k)
            right = get(k + 1, j)
            for a in left:
                for b in right:
                    s.add(a + b)
                    s.add(a - b)
                    s.add(a * b)
                    if b != 0:
                        s.add(a / b)

        dp[i][j] = s
        return s

    reachable = get(0, 8)

    ans = sum(f.numerator for f in reachable
              if f.denominator == 1 and f.numerator > 0)
    print(ans)

if __name__ == "__main__":
    solve()