Subtask 1 was intended to permit simple case-analysis based solutions.

Subtask 2 was intended to permit brute force search solutions.

Subtask 3 was a reduction to a standard Dynamic Programming problem (commonly stated as: you have certain coins, find if you can pay exactly $X$ amount of money with them).

Subtask 4 was intended to permit task-specific but suboptimal Dynamic Programming solutions.

The full solution uses Dynamic Programming. Let us mentally reorder the hours spent on each meal such that for the first $K$ hours, all chefs are different. This way we can visualize these $K$ hours forming an $N\times K$ "diversity box", with all "non-diverse hours" coming afterwards (as shown in the figure above). Now let's make the following observations:

1. Each chef can add at most $1$ hour to any column of the "diversity box".
2. A chef $j$ can fill the "diversity box" by at most $min(B_j,N)$.
3. In a correct solution, the "diversity box" must be filled by an amount of at least $N\times K$.
4. Suppose you have decided to hire chefs for a total of $H$ hours. Then it's optimal to hire such set of chefs that the "diversity box" is filled as much as possible (perhaps even overfilled).

Now let $D[c][h]$ be the maximum amount we can fill the "diversity box" by picking a subset of chefs $1,\dots ,c$ such that they are hired for a total of $h$ hours. Now let us notice that for the value $D[c][h]$ there are two possibilities:

1. The maximal subset contains chef $c$. Thus the other chefs in this subset form a maximal solution for $D[c-1][h-B_c]$ (otherwise we could pick a better subset). Thus $D[c][h]=D[c-1][h-B_c]+min(B_c,N)$.
2. The maximal subset doesn't contain chef $c$. Thus this subset also forms a maximal solution for $D[c-1][h]$ (a better solution to $D[c-1][h]$ would contradict the maximality of this subset). Thus $D[c][h]=D[c-1][h]$.

Now we simply need to consider the two cases and see which gives us a better solution. Thus $D[c][h]=max(D[c-1][h-B_c]+min(B_c,N),D[c-1][h])$. For performing the dynamic programming computation, we can initialize $D[0][0]$ to $0$ and every other $D[i][j]$ to $\mathrm{\infty }$. Note that once we have computed $D[c][\ast ]$ we don't care about $D[c-1][\ast ]$ anymore, so we can optimize memory consumption. The answer will be minimum non-negative $h-\sum _i{A}_i$ such that $D[N][h]\ge N\times K$.

Credits

• Task: Bernhard Linn Hilmarsson (Iceland)
• Solutions and tests: Oliver-Matis Lill, Andres Unt (Estonia)