Contest link: https://mirror.codeforces.com/gym/100430
100430A - Chip Installation
100430B - Divisible Substrings
100430C - Preparing Documents
100430D - GridBagLayout
100430E - Hot Potato Routing
100430F - Knapsack Problem
For a subset $$$A \subset {1, \ldots, n}$$$ we introduce the notation
for convenience. First, note that $$$\mathcal{I}$$$ always contains $$$\varnothing,$$$ since $$$s(\varnothing) = 0$$$. As a result we cannot violate condition $$$1.$$$ Similarly, it is impossible to violate condition $$$2,$$$ since for $$$A \supset B$$$ we have
and $$$s(A \setminus B) \geq 0$$$ by non-negativity of the weights $$$w_i.$$$
We say a set $$$A$$$ is constrained if $$$s(A) \leq c$$$ and for all $$$x \not \in A,$$$ $$$s(A \cup {x}) \geq c.$$$ Clearly if we can find constrained sets $$$A, B$$$ with $$$|A| \neq |B|$$$ then we have a contradiction to the third condition.
Consider the sets $$$M_{\min}$$$ and $$$M_{\max}$$$ constructed as follows:
For $$$M_{\min},$$$ iterate through the indices $$${1,\ldots, n}$$$ in non-decreasing order of $$$w_i.$$$ At each index, if adding it to the set keeps $$$s(M_{\min})$$$ at most $$$c,$$$ then add it to $$$M_{\min}.$$$ For $$$M_{\max},$$$ perform the same algorithm with the indices initially in non-increasing order of weights.
It is well known that $$$M_{\min}$$$ is the constrained set with the maximum size and $$$M_{\max}$$$ is the constrained set of minimum size. I leave it as an exercise to prove this.
If $$$|M_{\min}| \gt |M_{\max}|$$$ then we are done. Otherwise, we know that all constrained sets have the same size; call this $$$k.$$$
We now make the following claim: If $$$|A| \gt |B|$$$ are sets which contradict property $$$3$$$, then there exist sets $$$C \supset A$$$ and $$$D \supset B$$$ such that $$$|C| = k$$$ and $$$|D| = k - 1$$$ which also contradict this property. We split the proof of this claim into two lemmas.
Lemma 1. If $$$|A| \lt k$$$ then we can construct $$$|C| = k.$$$
Proof: Since $$$|B| \lt |A| \lt k$$$ neither of these sets are constrained. Then there exist indices $$$i,j$$$ which can be added to $$$B$$$ and $$$A$$$ respectively. We can add $$$x = \argmin_{u \in {i,j}} w_u$$$ to both sets. The proof is completed by induction.
Lemma 2. If $$$|A| - |B| \gt 1$$$ then we can construct $$$|C| - |D| = 1.$$$
Proof:
