## Editorial for An Animal Contest 4 P1 - Dasher's Digits

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

#### Subtask 1

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.

**Time Complexity:**

#### Subtask 2

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**.

**Time Complexity:**

#### Subtask 3

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

## Comments