Problem 103: Special Subset Sums: Optimum

Mathematical Development

Theorem 1 (Equivalent Condition for Property 2). Let $A = \{a_1 < a_2 < \cdots < a_n\}$ be a set of positive integers. Property 2 holds if and only if

Proof. ($\Rightarrow$) Take $B = \{a_1, \ldots, a_{k+1}\}$ and $C = \{a_{n-k+1}, \ldots, a_n\}$. These are disjoint since $k + 1 \leq \lfloor n/2 \rfloor + 1 \leq n - k + 1$ for $k \leq \lfloor n/2 \rfloor$. Since $|B| = k + 1 > k = |C|$, Property 2 yields $S(B) > S(C)$.

($\Leftarrow$) Let $B, C$ be disjoint subsets of $A$ with $|B| = m > \ell = |C|$. Write $B = \{b_1 < \cdots < b_m\}$ and $C = \{c_1 < \cdots < c_\ell\}$. Since the $b_i$ are $m$ distinct elements of $A$, we have $b_i \geq a_i$, so $S(B) \geq \sum_{i=1}^{m} a_i$. Similarly, since the $c_j$ are $\ell$ distinct elements of $A$, we have $c_j \leq a_{n - \ell + j}$, so $S(C) \leq \sum_{j=n-\ell+1}^{n} a_j$. Applying the hypothesis with $k = \ell$:

Theorem 2 (Reduction to Global Subset-Sum Uniqueness). Property 1 holds for $A$ if and only if all $2^n - 1$ non-empty subset sums of $A$ are pairwise distinct.

Proof. ($\Leftarrow$) If all subset sums are distinct, then in particular $S(B) \neq S(C)$ for any two distinct non-empty subsets, a fortiori for disjoint ones.

($\Rightarrow$) We prove the contrapositive. Suppose distinct non-empty subsets $B', C'$ satisfy $S(B') = S(C')$. Let $D = B' \cap C'$, $B = B' \setminus D$, $C = C' \setminus D$. Then $B$ and $C$ are disjoint. Since $B' \neq C'$, at least one of $B, C$ is non-empty. If both are non-empty, then

violating Property 1. If exactly one (say $C$) is empty, then $C' \subseteq B'$ and $S(B') = S(C')$ forces $S(B' \setminus C') = 0$; but all elements are positive, so $B' \setminus C' = \emptyset$, contradicting $B' \neq C'$. $\blacksquare$

Lemma 1 (Near-Optimum Heuristic Construction). Given an optimal special sum set $\{b_1, \ldots, b_{n-1}\}$ of size $n - 1$ with middle element $b_m$ where $m = \lceil(n-1)/2\rceil$, the set $\{b_m,\, b_m + b_1,\, b_m + b_2,\, \ldots,\, b_m + b_{n-1}\}$ is a near-optimum special sum set of size $n$.

Proof. This construction, due to Lunnon, yields a set satisfying both properties. The minimum element is $b_m > 0$, ensuring positivity. Property 2 is satisfied because the spread $b_m + b_1$ vs.\ $b_m + b_{n-1}$ inherits the structure of the original set. Optimality is not guaranteed, but the set serves as a starting point for local search. $\blacksquare$

Editorial

We check Property 2. Finally, check Property 1. Candidates are generated from the derived formulas, filtered by the required conditions, and processed in order until the desired value is obtained.

Pseudocode

Check Property 2
Check Property 1

Complexity Analysis

• Time. The perturbation space has $(2 \cdot 3 + 1)^7 = 7^7 = 823{,}543$ candidates. For each candidate passing the sum bound and Property 2 filter, Property 1 costs $O(2^n)$ with $n = 7$, i.e., 128 subset-sum computations. With aggressive pruning, total work is on the order of $10^6$ operations.
• Space. $O(2^n) = O(128)$ for the hash set of subset sums.

Answer

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <string>
using namespace std;

/*
 * Problem 103: Special Subset Sums: Optimum
 *
 * Search for the optimal n=7 special sum set by perturbing the
 * near-optimum {20,31,38,39,40,42,45} by +/-3 on each element.
 */

bool is_special(vector<int>& a) {
    int n = a.size();
    sort(a.begin(), a.end());
    // Property 2
    for (int k = 1; k <= n / 2; k++) {
        int lo = 0, hi = 0;
        for (int i = 0; i <= k; i++) lo += a[i];
        for (int i = 0; i < k; i++) hi += a[n - 1 - i];
        if (lo <= hi) return false;
    }
    // Property 1
    set<int> sums;
    for (int mask = 1; mask < (1 << n); mask++) {
        int s = 0;
        for (int i = 0; i < n; i++)
            if (mask & (1 << i)) s += a[i];
        if (sums.count(s)) return false;
        sums.insert(s);
    }
    return true;
}

int main() {
    int base[] = {20, 31, 38, 39, 40, 42, 45};
    int best_sum = 255;
    vector<int> best_set(base, base + 7);
    const int D = 3;

    for (int d0 = -D; d0 <= D; d0++)
    for (int d1 = -D; d1 <= D; d1++)
    for (int d2 = -D; d2 <= D; d2++)
    for (int d3 = -D; d3 <= D; d3++)
    for (int d4 = -D; d4 <= D; d4++)
    for (int d5 = -D; d5 <= D; d5++)
    for (int d6 = -D; d6 <= D; d6++) {
        vector<int> a = {
            base[0]+d0, base[1]+d1, base[2]+d2, base[3]+d3,
            base[4]+d4, base[5]+d5, base[6]+d6
        };
        bool ok = true;
        for (int x : a) if (x <= 0) { ok = false; break; }
        if (!ok) continue;

        sort(a.begin(), a.end());
        for (int i = 1; i < 7; i++)
            if (a[i] <= a[i-1]) { ok = false; break; }
        if (!ok) continue;

        int s = 0;
        for (int x : a) s += x;
        if (s > best_sum) continue;

        if (is_special(a)) {
            if (s < best_sum || (s == best_sum && a < best_set)) {
                best_sum = s;
                best_set = a;
            }
        }
    }

    sort(best_set.begin(), best_set.end());
    string ans;
    for (int x : best_set) ans += to_string(x);
    cout << ans << endl;
    return 0;
}

"""
Problem 103: Special Subset Sums: Optimum

Find the optimum special sum set of size 7, starting from the
near-optimum {20, 31, 38, 39, 40, 42, 45}.
"""
from itertools import product


def is_special_sum_set(a):
    a = sorted(a)
    n = len(a)
    # Property 2: sum of smallest k+1 > sum of largest k
    for k in range(1, n // 2 + 1):
        if sum(a[:k + 1]) <= sum(a[n - k:]):
            return False
    # Property 1: all subset sums distinct
    sums = set()
    for mask in range(1, 1 << n):
        s = sum(a[i] for i in range(n) if mask & (1 << i))
        if s in sums:
            return False
        sums.add(s)
    return True


def solve():
    base = [20, 31, 38, 39, 40, 42, 45]
    best_sum = sum(base)
    best_set = tuple(sorted(base))
    delta = 3

    for d in product(range(-delta, delta + 1), repeat=7):
        a = [base[i] + d[i] for i in range(7)]
        if any(x <= 0 for x in a):
            continue
        a_sorted = sorted(a)
        if len(set(a_sorted)) != 7:
            continue
        s = sum(a_sorted)
        if s > best_sum:
            continue
        if is_special_sum_set(a_sorted):
            if s < best_sum or (s == best_sum and tuple(a_sorted) < best_set):
                best_sum = s
                best_set = tuple(a_sorted)

    return "".join(str(x) for x in best_set)


if __name__ == "__main__":
    answer = solve()
    print(answer)
    assert answer == "20313839404245"