Editorial for COCI '13 Contest 5 #3 Eksplozjia

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.

A simple solution which literally simulates the described procedure of chain reaction (finds the first appearance of the explosion, deletes it, concatenates the rest of the string and repeats this procedure) is not fast enough because of the limitations (1 \le |Mirko's string| \le 1\,000\,000).

One of the faster solutions uses hashing. But, given the fact that the explosion consists of only different characters (uppercase and lowercase letters of the English alphabet and digits 0, 1, …, 9), it is possible to come up with a solution in linear complexity which uses a stack to keep track of certain data during the string analysis.

The string analysis is done in the following way: we scan Mirko's string character by character. Because the stack is used to quickly identify the explosion, it will keep track of the position in the explosion. During the analysis, two main situations can happen:

  1. The current character is equal to a possible beginning of the explosion: mark this position and remember it (push it on the stack).

  2. The current character is not equal to a possible beginning of the explosion (and the stack is not empty):

    • the current remembered position in the explosion on the stack fits the current character in the string: move this position forward in the explosion and push it back on the stack (it is possible that in this step we have reached the end of the explosion, which means we have located it in the string so it is necessary to mark the beginning and the end of the explosion for later deletion and then we don't push it back on the stack)

    • the current remembered position in the explosion on the stack doesn't fit the current character in the string: empty the whole stack (we leave this question to the reader, as to why we are discarding the whole stack in this situation)

When we finish scanning the string, it is necessary to delete the marked explosions in the string in one pass.

This way, using the stack, we have made sure that our algorithm works in situations when deleting an explosion and concatenating the rest of the string produces new explosions.

A special case is when the length of the explosion is 1.

Comments

There are no comments at the moment.