← CSES Better

Recover a Sum from All Subset Sums

ZIO · 2024 · Zonal Informatics Olympiad · P1

Open official problem ↗
Ask AI

Open a hint-first prompt in a new AI chat. Grok may ask you to confirm before sending.

Open Claude Desktop

math · subsets · invariants

The organizer’s problem statement is available at the official source link.

flow

Every element appears in half the subsets

Across the complete list of subset sums, each array value contributes exactly 2^(N-1) times.

State table
AggregateCoefficientUnknown
all subset sums2^(N-1)sum(A_i)
S2^(N-1)S / 2^(N-1)
  1. 1

    Enumerate subsets

    The empty subset and all 2^N element subsets contribute one sum each.
  2. 2

    Count each value

    Fix Ai: every choice of the other N−1 elements creates one subset containing Ai.
  3. 3

    Divide the aggregate

    The sum of all listed subset sums is 2^(N−1) × (A1 + … + AN).
Tools
1
2
3
4
5
6
7
8
9
10
11
12
Draft saved locally
|12 lines, 156 chars

Run output

Run your code to see output.