Editorial for An Animal Contest 4 P1 - Dasher's Digits
Submitting an official solution before solving the problem yourself is a bannable offence.
Due to the cyclic nature of the algorithm, it suffices to simulate the algorithm until we encounter the
0 at the front of the string, at which point it can be removed and the remaining characters outputted in order.
If , note that we care only about the
0 that is removed last. This can be done by comparing values, breaking ties by comparing the indices at which the
0's appear in the input string. We can then remove the
0 that is removed first without any consequence.
From this point onwards, we can perform the same sort of simulation as outlined in Subtask 1.
We still only care about the last
0 that is removed. We can find the index of this
0 by sorting the
0's based on their value and breaking ties by selecting the
0 that is further back. Let's call the index of this last
0 . We now separate the number into two strings and , where contains all non-
0 characters in the input order before , and contains all the non-
0 characters in the input order after . When we reach for the last time, the string can be shown to be , where represents concatenation.
A slightly faster solution involves maintaining by iterating through the string instead of sorting.
Time Complexity: or