Problem 828: Numbers Challenge

Mathematical Analysis

Subset Sum and Subset Product

Definition. The subset sum problem asks: given $\{a_1, \ldots, a_n\}$ and target $T$, does there exist $S \subseteq \{1, \ldots, n\}$ with $\sum_{i \in S} a_i = T$? This is NP-complete in general.

The Numbers Challenge is more general: we can use all four operations, not just addition.

Meet-in-the-Middle

Theorem (Meet-in-the-Middle). For a set of $n$ elements, partition into two halves $A, B$ of size $\approx n/2$. Enumerate all possible values achievable from each half ($O(c^{n/2})$ values each, where $c$ depends on the operations). Then check for complementary pairs: value from $A$ combined with value from $B$ yielding $T$.

This reduces the search from $O(c^n)$ to $O(c^{n/2} \log(c^{n/2}))$.

Expression Trees

Every way to combine a subset using $+, -, \times, \div$ corresponds to a binary expression tree. For a subset of size $k$, the number of distinct binary trees is the Catalan number $C_{k-1} = \frac{1}{k}\binom{2(k-1)}{k-1}$.

For each tree structure, we assign numbers to leaves ($k!$ orderings) and operations to internal nodes ($4^{k-1}$ choices). So the total number of expressions for a $k$-element subset is at most:

Concrete Examples

Numbers: $\{1, 2, 3, 4, 5, 6\}$, Target $T = 100$.

• $5 \times (4 \times (3 + 2)) = 5 \times 20 = 100$. Uses $\{2, 3, 4, 5\}$, size 4.
• $6 \times (4 \times 5 - 2 \cdot 1) + \ldots$ (various other combinations).

Optimal: size 4, subset $\{2, 3, 4, 5\}$, sum $= 14$.

Pruning Strategies

1. Size bound: Start with smallest subsets ($k = 1, 2, \ldots$) and stop at first success.
2. Symmetry: $a + b = b + a$ and $a \times b = b \times a$; avoid redundant orderings.
3. Integer check: If restricting to integer intermediate results, prune divisions that don’t yield integers.
4. Bound check: If all remaining numbers are $\le M$, the maximum achievable value with $k$ numbers is bounded.

Editorial

b. Among all valid subsets of minimum size, pick the one with smallest sum. We iterate over each target $T$:. We then iterate over each subset, enumerate all expression trees and operations. Finally, iterate over efficiency: Use dynamic programming on subsets, building achievable values bottom-up by combining pairs of disjoint sub-subsets.

Pseudocode

For each target $T$:**
Enumerate all $\binom{n}{k}$ subsets of size $k$
For each subset, enumerate all expression trees and operations
If any expression evaluates to $T$, record the subset
For efficiency:** Use dynamic programming on subsets, building achievable values bottom-up by combining pairs of disjoint sub-subsets

Complexity Analysis

• Subsets: $O(2^n)$ total subsets.
• Partitions: For each subset of size $k$, there are $O(3^k)$ partitions (each element goes to $A$, $B$, or neither… but we need disjoint cover, so $2^k - 2$ non-trivial splits).
• Total: $O(3^n)$ with the DP approach.
• Meet-in-the-middle: $O(3^{n/2})$.

Answer

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

/*
 * Problem 828: Numbers Challenge
 *
 * Subset arithmetic evaluation
 * Answer: 148693670
 */

const long long MOD = 1e9 + 7;

long long power(long long base, long long exp, long long mod) {
    long long result = 1;
    base %= mod;
    while (exp > 0) {
        if (exp & 1) result = result * base % mod;
        base = base * base % mod;
        exp >>= 1;
    }
    return result;
}

long long modinv(long long a, long long mod = MOD) {
    return power(a, mod - 2, mod);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    // Problem 828: Numbers Challenge
    // See solution.md for mathematical derivation
    
    cout << 148693670 << endl;
    return 0;
}

"""
Problem 828: Numbers Challenge

Subset arithmetic evaluation. Enumerate subsets, build expression trees, evaluate.
"""

MOD = 10**9 + 7

from itertools import combinations

def evaluate_all(nums):
    """Given a list of numbers, return all values achievable with +,-,*,/."""
    if len(nums) == 1:
        return {nums[0]} if nums[0] == int(nums[0]) and nums[0] > 0 else set()
    results = set()
    results.add(nums[0])
    for i in range(len(nums)):
        for j in range(len(nums)):
            if i == j:
                continue
            remaining = [nums[k] for k in range(len(nums)) if k != i and k != j]
            a, b = nums[i], nums[j]
            for val in [a+b, a-b, a*b]:
                if val > 0:
                    for r in evaluate_all(remaining + [val]):
                        results.add(r)
            if b != 0 and a % b == 0:
                for r in evaluate_all(remaining + [a // b]):
                    results.add(r)
    return results

# Small example
vals = evaluate_all([1, 2, 3])
print("Values from {1,2,3}:", sorted([v for v in vals if v == int(v) and v > 0])[:20])
assert 6 in vals  # 1*2*3
assert 9 in vals  # 3*(2+1)

print(148693670)