## 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 for all , any set of moves that results in a positive 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 :

• the number of balls that are moved from the range to the range .
• the number of balls that are moved from the range to the range .

Note that by definition, we must have , and furthermore since the number of balls in each segment must be the same. Initially, and . To obtain the values of and for larger , consider performing moves centered at index and moves that move a ball from to . Clearly should be no larger than and should be no larger than , and we must also have since there is no other way to get rid of any excess balls at index .

After these moves are determined, we have nice formulas for and :

• • Note that we add to since we introduce new balls that move from to , and we subtract since we no longer consider the balls that move from to . The formula for can be derived in a similar manner.

If we consider all possible values of and at every index, then it is only possible if we can reach and 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 and always form a consecutive interval of integers. Thus, it suffices to only track the minimum and maximum possible values of and at each index. These may be computed greedily in time each, which is fast enough for the given constraints.

Time Complexity: Credit goes to azeng for discovering this elegant solution.