Editorial for WC '17 Contest 2 J4 - Entish Translation


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.

One approach to this problem involves taking two separate passes over the text, one for each step of the translation process – first collapsing all contiguous sequences of consonants, and then parsing the string into tokens and collapsing all contiguous sequences of equal ones. A simple way of performing both types of reductions is to iterate over the characters/tokens, keep track of the previous one, and use it to determine whether or not the current one should be removed. It's possible to either modify the string in place by deleting characters, or create a new string from the new characters which should be kept.

In the official solution, we instead combine everything into a single pass over the characters of the text, while keeping track of several pieces of information – the answer string (which is gradually built up from the appropriate characters/tokens), the current token string, the previous token, and the previous character. When a letter is processed, it should be added onto the current token unless both this letter and the previous character are consonants. When a dash is processed or the end of the text is reached, the current token should be appended to the answer string unless it's equal to the previous token (if any), and then the current token should be reset to an empty string.


Comments

There are no comments at the moment.