Editorial for DMOPC '21 Contest 9 P2 - String Puzzle


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: 4fecta

Subtask 1

Iterate through both strings simultaneously. Any excess as in A must be merged with another a immediately behind to match the b correctly in B. If the character behind is not a or there is an extraneous b in A, we can evaluate the case to be impossible.

Time Complexity: \mathcal{O}(\sum (|A| + |B|))

Subtask 2

Similar to the first subtask, if a character in A is less than the target character in B, we must repeatedly try to merge it with further characters in A until they match. This can be implemented either recursively or iteratively using a stack.

Time Complexity: \mathcal{O}(\sum (|A| + |B|))

Alternately, note that if we let o(c) be the order of the character c in the alphabet, then the quantity \sum 2^{o(c)} remains invariant over all operations. Thus, we can instead imagine repeatedly splitting the characters of B back into A. For each split, there can be at most one candidate splitting point in A, which can be found by binary searching on the prefix sums of 2^{o(c)}.

Time Complexity: \mathcal{O}(\sum (|A| \log |A| + |B|))


Comments

There are no comments at the moment.