## Editorial for DMOPC '20 Contest 2 P4 - Hungry Pigeons

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

Author: PrimeNet

A brute force algorithm will suffice for this subtask. After the -th minute, simply consider all ways of assigning the first worms to the pigeons.

Time complexity:

A slightly better brute force algorithm is required for this subtask. Rather than consider all possible ways of assigning the worms, it can be quickly realized that the smallest worms should be assigned to the smallest pigeons.

First, we will need to sort the beak sizes. After the -th minute, we should also sort the first worm diameters. Then, we can find the maximum possible flock satisfaction by linearly searching for it. In other words, for all , we should try to feed the smallest worms to the smallest pigeon, then feed the next smallest worms to the next smallest pigeon, and so on. If this assignment works, then is a possible flock satisfaction; otherwise, is not.

Time complexity:

This subtask requires the following observation:

Lemma: For all , define the "sub-satisfaction" of the -th smallest pigeon to be the number of worms that pigeon can eat, divided by (and rounded down). Then, the maximum possible satisfaction of the flock equals the minimum sub-satisfaction among all pigeons.

The rationale for this observation is as follows: Using the greedy algorithm explained in Subtask 2, if we try to feed worms to every pigeon, the largest worm that the -th smallest pigeon will eat is the ()-th smallest worm. If is larger than or equal to the pigeon's sub-satisfaction, then the pigeon can eat the worm; otherwise, the pigeon cannot. Using this lemma, we can now develop the following algorithm: First, we need to sort the beak sizes. We will need to keep track of the number of worms each pigeon can eat over time. After the -th minute, we need to update these counts for the pigeons, based on whether or not each pigeon can eat the -th worm. Then, we can easily compute the sub-satisfaction of each pigeon after each minute, which allows us to find the maximum possible satisfaction of the ock.

Time complexity: