Editorial for DMOPC '17 Contest 4 P6 - Best Girl


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

For the first subtask, greedily form prefixes of MAKI. For each type 2 operation, loop through the letters and keep track of how many of each prefix can be formed (all at once).

Time Complexity: \mathcal O(QN)

For the second subtask, consider greedily forming substrings of MAKI. For example, if a K is encountered and there is a MA substring, then attach the K to the MA. If not, but there is an A substring, then create the AK substring. If neither of those exist, create the K substring. The number of each substring which may be formed as subsequences over a substring of S can be represented as a 4 by 4 array. Now create a segment tree where each node of the segment tree is that 4 by 4 array for the node's substring of S.

The main difficulty in this solution is merging the 4 by 4 arrays of two sections of S. Consider the substrings of the left section of S by prioritizing the starting character of each substring and then prioritizing by length. For each of these substrings, a longer one can be created by using the characters of the right section of S. Now when merging these substrings, it's important that the middle overlap is treated properly. In this case, the middle overlap should be treated as if this substring exists in a section between the left and right section. That is because there is a choice of whether to take the overlap from the left or the right.

Time Complexity: \mathcal O(Q\log N)


Comments

There are no comments at the moment.