Editorial for DMOPC '22 Contest 2 P5 - Beautiful Bins


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: 4fecta

First of all, note that since we have A_i \geq 1 for all i, any set of moves that results in a positive B will always have an ordering of the moves such that none of the quantities ever go negative. Thus, the only thing that matters is the number of each move performed.

To reach a solution, consider maintaining the following two quantities at each index i:

  • l_i := the number of balls that are moved from the range [i, N] to the range [1, i-1].
  • r_i := the number of balls that are moved from the range [1, i-1] to the range [i, N].

Note that by definition, we must have l_i, r_i \geq 0, and furthermore r_i - l_i = \sum_{k=1}^{i-1}(A_k - B_k) since the number of balls in each segment must be the same. Initially, l_2 = B_1 - A_1 and r_2 = 0. To obtain the values of l_i and r_i for larger i, consider performing s moves centered at index i and x moves that move a ball from [1, i-1] to i. Clearly s should be no larger than l_i and x should be no larger than r_i, and we must also have A_i - 2s + x \leq B_i since there is no other way to get rid of any excess balls at index i.

After these moves are determined, we have nice formulas for l_{i+1} and r_{i+1}:

  • l_{i+1} = l_i + s - x + B_i - A_i
  • r_{i+1} = r_i + s - x

Note that we add s to r_i since we introduce s new balls that move from i to [i+1, N], and we subtract x since we no longer consider the x balls that move from [1,i-1] to i. The formula for l_{i+1} can be derived in a similar manner.

If we consider all possible values of s and x at every index, then it is only possible if we can reach l_N = 0 and r_N = B_N - A_N in the end. The issue, however, is that this is far too slow on any reasonably sized input. To speed the solution up, note that the possible values of l_i and r_i always form a consecutive interval of integers. Thus, it suffices to only track the minimum and maximum possible values of l_i and r_i at each index. These may be computed greedily in \mathcal{O}(1) time each, which is fast enough for the given constraints.

Time Complexity: \mathcal{O}(N)

Credit goes to azeng for discovering this elegant solution.


Comments

There are no comments at the moment.