Editorial for IOI '12 P3 - Crayfish Scrivener

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 clever way to get an efficient solution consists in representing the evolution of the system through a trie, containing all the contents of the text so far; a point in time is represented by a single pointer to a node in the trie.

Command processing requires $\mathcal O(1)$ ~\mathcal O(1)~ time:

typing a letter just requires moving down in the trie (creating a new node if necessary)
undoing $K$ ~K~ commands requires moving $K$ ~K~ states back.

For all the subtasks except the final one, after processing all the commands, the final contents can be extracted from the trie into an array and used to answer queries in $\mathcal O(1)$ ~\mathcal O(1)~ time, giving $\mathcal O(N)$ ~\mathcal O(N)~ time and space overall.

Subtask 5 requires a definitely more sophisticated approach to find a point in the text. For this it is sufficient to be able to determine the $k$ ~k~-ancestor of the current node: There are a number of standard data structures for this problem that give $\mathcal O(N \log N)$ ~\mathcal O(N \log N)~ time overall. For example, every node at depth $D$ ~D~ can contain a pointer to its $2^k$ ~2^k~-th ancestor, where $k$ ~k~ is the position of the rightmost $1$ ~1~ in the binary expansion of $D$ ~D~.

Comments

There are no comments at the moment.