Editorial for COCI '20 Contest 1 #2 Bajka
Submitting an official solution before solving the problem yourself is a bannable offence.
Let us denote the scary word by , and the favourite word by .
We use dynamic programming. State means that we are on the position in the scary word, and we want to write down the letter of the favourite word. The transition is given by , where is the time cost for the transition. The transition can be done for each pair of positions such that , , and either or exists and is equal to . We first move from position to either position or position , whichever is equal to , using the second kind of move, and then to position using the first kind of move (so we will write down ). The cost is the sum of costs of the two moves. We need to be careful when both positions and contain and take the one that is closer.
The time complexity is . The problem can be solved in complexity, but that is left as an exercise to the reader.
Comments