CF 1500E - Subset Trick
The task revolves around reasoning about subset sums in a set of distinct positive integers. You are given an initial set $S$ and a series of operations that either add or remove elements.
Rating: 3300
Tags: binary search, data structures
Solve time: 56s
Verified: no
Solution
Problem Understanding
The task revolves around reasoning about subset sums in a set of distinct positive integers. You are given an initial set $S$ and a series of operations that either add or remove elements. For any positive integer $x$, we call it unsuitable if knowing only the size of a chosen subset is insufficient to determine whether the sum of that subset exceeds $x$. The goal is to count how many integers are unsuitable for the current set after every change.
The input gives $n$, the number of initial integers, followed by the integers themselves, and then $q$ queries that modify the set. Each query either adds a new integer (not already in the set) or removes an existing integer. The output is a sequence of $q+1$ integers representing the count of unsuitable numbers for the initial set and after each change.
The constraints imply that $n$ and $q$ can be as large as 200,000, and each integer can be up to $10^{13}$. A brute-force check over all possible subset sums is infeasible because the number of subsets is $2^n$, which grows exponentially. Operations on large integers must be handled without overflow. Edge cases include empty sets, sets with widely spaced numbers, and adding or removing elements that are very large compared to the rest. For example, with $S = {1, 10^{13}}$, the sums of subsets jump from 0, 1, $10^{13}$, to $10^{13}+1$, producing a very different set of unsuitable numbers than a contiguous small set would.
Approaches
The naive approach is to enumerate all subsets of $S$, group them by size, and then determine the ranges of sums for each subset size. For each $x$, you would check if the maximum sum of a subset of size $k$ is less than or equal to $x$ while the mi