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

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

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: \mathcal{O}(N)

Subtask 2

If M = 2, note that we care only about the 0 that is removed last. This can be done by comparing a_i 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: \mathcal{O}(N)

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 a_i value and breaking ties by selecting the 0 that is further back. Let's call the index of this last 0 i. We now separate the number into two strings A and B, where A contains all non-0 characters in the input order before i, and B contains all the non-0 characters in the input order after i. When we reach i for the last time, the string can be shown to be B + A, where + represents concatenation.

A slightly faster solution involves maintaining i by iterating through the string instead of sorting.

Time Complexity: \mathcal{O}(N \log N) or \mathcal{O}(N)


There are no comments at the moment.