Penguins#495

Penguins (Editorial)

Author: Timur Degteari

Prepared by: Timur Degteari Editorial prepared by: Timur Degteari, Kostiantyn Denysov

We claim that the answer . Indeed, consider the following greedy approach:

  • go through families, assign the current family to the team of the smallest size. Consider how the smallest team size and the largest team size change:

  • let be the minimum and be the maximum. Suppose y-x \le 3. Then after assigning the current family to the smallest team, new minimum is at least , and the new maximum is \max(x+3, y) \le x+3. Hence the property holds throughout the assignment process.

Hence answer is always one of 0, 1, 2, 3.

Let be the number of families with penguins, with penguins, and with penguin. Let S = 3 \cdot x + 2 \cdot y + z.

Claim: if (x\ \%\ k) > 0 and (x\ \%\ k) + y + z < k, the answer is .

Let t = \lfloor \frac{x}{3} \rfloor. First observe that in an optimal assignment at least one team will have penguins. Since (x\ \%\ k) + y + z < k, by pigeonhole principle at least one team will contain only -penguin families. If that team has size 3t+3, then for answer to not be , all other teams must have sizes \ge 3t+1, so each of them must contain either at least one family of size or , or at least t+1 families of size , hence (x\ \%\ k) + y + z \ge k-1. At the same time, the team we're considering also has t+1 families of , so (x\ \%\ k) + y + z \ge k, a contradiction.

If that team has size at most 3t-3, then by pigeonhole principle, largest team has size at least \frac{S}{k} > 3t, which gives answer , contradiction. Hence there always is at least one team with size .

Furthermore, this is the only case when answer is . Suppose (x\ \%\ k) + y + z \geq k. First evenly distribute families of among the teams, so that teams have 3t+3 penguins and remaining teams have penguins. Now distribute enough and -penguin families so that all team have sizes between 3t+1 and 3t+3. Since only families of and are left, and the size difference is at most , we can keep it at most by greedily adding new family to the smallest team, hence optimal answer is at most .

Additionally, if (x\ \%\ k) + y + z < k, but (x\ \%\ k) = 0, clearly answer is if y > 0; if y=0, z>0, and if y=z=0.

Hence now, we only need to distinguish between whether answer is , or .

Targets for answers 0 and 1.

Checking ans=0. If S\bmod k\ne 0, then ans=0 is impossible. Otherwise all teams must have the same size T=S/k.

Checking ans=1. Let L=\lfloor S/k\rfloor, U=L+1, and x=S-kL. Then exactly teams must have size and the remaining k-x teams must have size .

In both cases we run the same feasibility procedure TryBuild that attempts to construct teams with the required target sizes using the available families.

Greedy feasibility procedure TryBuild.

We are given a multiset of target team sizes (either all , or k-x copies of and copies of ). We also maintain remaining counts (c_1,c_2,c_3) and try to build each team independently.

First pass (pattern-based greedy). For each target size (process targets in nondecreasing order), we try to fill one team of total sum exactly by the following priorities:

  1. If is odd, place one family of size if possible; otherwise place one family of size . Decrease by or respectively. If neither is available, this pass fails.

  2. While possible, place pairs (subtract from ) as long as t\ge 6.

  3. Then, while possible, place pairs (subtract ), but only after finishing the step.

  4. Then place as many -families as possible (subtract each time).

  5. Finally, place pairs (subtract ).

If we manage to reduce every target to , the first pass succeeds; otherwise it fails.

Second pass (largest family into smallest team). If the first pass fails, we restart from the original counts and run another greedy:

  • Keep teams with their current sums (initially all ) in a structure that can return the currently smallest-sum team.

  • Repeatedly take the largest remaining family (prefer size , then , then ) and add it to the currently smallest team.

After all families are assigned, we sort the obtained team sums and compare them with the required target multiset. If they match, the second pass succeeds.

Complexity.

Counting c_1,c_2,c_3 is . The second greedy pass can be implemented with a priority queue over teams and runs in O(n\log k). Overall complexity per test case is O(n\log k).