I failed to solve it because:

  1. Tried reducing to partition optimization problem, realize it has no easy/efficient solution

  2. Saw the simple greedy insight for small case, and yet, I was not able to prove it.

The excercise proof from contest analysis

Given there exists an optimal solution where all but 0 or 1 of each problem solutions belong to advancers. We claim F(C,n) = sum(S)/C

Proof: Induction on the value of F(C,n) = k

notice there we can not have more than C problems whose solutions has 1 unused by advancers. Otherwise, we can advance 1 more instead. By this fact, we also know at least N-C + 1 problems whose solutions are used by all advancers.

If we take out 1 solve from C problems, while ensuring we take out ones from ones with solutions unused by advancers. We know that we will end up with a state where

  1. the problems with unused solutions now all become fully used

  2. some of the problems without unused solutions become with 1, unused solution, but this number <= C, because we make C changes in total

i.e., we reach the inductive state for k - 1. Adding these C solves back gives the result we need.

Proof of correctness for the divide and cap solution

Sort S, when k = sum(S)/C, and s[N] <= k, then F(C,n) = k

Proof: The general idea is similar to the one above

Induction on k,

Base case k = 0. Trivial

k case: Take 1 entries off from s[N-C +1] to S[N], kNew = k-1 = sum(SNew)/C

Because sum(S) = C * K, there are less than C entries with s[i] = k, otherwise, sum(S[i[) > sum(S) i.e., our operation ensures all S[i] <= k - 1, k-1 = sum(SNew)/C, by induction, at this time, F(C, n) = k - 1. Now we add the 1 entries back, allows one more to advance, i.e., F(C,n) = k.