Editorial for Canada Day Contest 2021 - CCC Bad Haha
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
Hint
In what cases will operating on a digit decrease the number?
Answer
When the digit is larger than the one after it.
Hint
The earlier digits always make a bigger difference than the later ones.
Solution
Given moves, Lookcook should move back the first
digits that are larger than the digit after it. These
digits can be found by keeping a monotonically nondecreasing stack. After finding these
values, move them in nondecreasing order (move the smallest of the
digits first and the largest last). This takes
time for an
digit number.
Example
1
26451689
5
is bigger than
. So
should be a digit that gets moved. The resulting number is
.
is bigger than
, so it should be moved. The resulting number is
.
Now that is directly after
,
should be moved. This leaves
.
Now that is directly after
,
should be moved. This leaves
.
is the last element. But we know that we will move
to the end, and it will be smaller than
. So
should also be moved, leaving
.
Should be moved for the same reason as
, but we've used up all our
operations, so we stop now.
The digits we've selected are
. They should be moved in the non-decreasing order
, giving the result as
.
Comments