Editorial for Canada Day Contest 2021 - CCC Bad Haha


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: Aaeria

Hint

In what cases will operating on a digit increase 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 K moves, Lookcook should move back the first K digits that are larger than the digit after it. These K digits can be found by keeping a monotonically nondecreasing stack. After finding these K values, move them in nondecreasing order (move the smallest of the K digits first and the largest last). This takes \mathcal O(n \log n) time for an n digit number.

Example

1
26451689
5

6 is bigger than 4. So 6 should be a digit that gets moved. The resulting number is 2451689.

5 is bigger than 1, so it should be moved. The resulting number is 241689.

Now that 1 is directly after 4, 4 should be moved. This leaves 21689.

Now that 1 is directly after 2, 2 should be moved. This leaves 1689.

9 is the last element. But we know that we will move 2 to the end, and it will be smaller than 9. So 9 should also be moved, leaving 168.

8 Should be moved for the same reason as 9, but we've used up all our 5 operations, so we stop now.

The K digits we've selected are \{6,5,4,2,9\}. They should be moved in the non-decreasing order 2,4,5,6,9, giving the result as 16824569.


Comments

There are no comments at the moment.