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

we introduce the notation

$ for convenience. First, note that

always contains

since

. As a result we cannot violate condition

Similarly, it is impossible to violate condition

since for

we have

$ and

by non-negativity of the weights

We say a set

is constrained if

and for all

Clearly if we can find constrained sets

with

then we have a contradiction to the third condition.

Consider the sets

and

constructed as follows:

For

iterate through the indices

in non-decreasing order of

At each index, if adding it to the set keeps

at most

then add it to

For

perform the same algorithm with the indices initially in non-increasing order of weights.

It is well known that

is the constrained set with the maximum size and

is the constrained set of minimum size. I leave it as an exercise to prove this.

If

then we are done. Otherwise, we know that all constrained sets have the same size; call this

100430G - Magic Potions

100430H - Restoring Permutation

100430I - Roads

100430J - Squary Set