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.$$$
