Editorial for DMOPC '22 Contest 2 P5 - Beautiful Bins
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
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
for discovering this elegant solution.
Comments