Editorial for COCI '20 Contest 1 #2 Bajka


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.

Let us denote the scary word by s, and the favourite word by f.

We use dynamic programming. State dp[i][j] means that we are on the i^\text{th} position in the scary word, and we want to write down the j^\text{th} letter of the favourite word. The transition is given by dp[i][j] = \min(dp[k][j+1]+c), where c is the time cost for the transition. The transition can be done for each pair of positions (i, k) such that s[i] = f[j], s[k] = f[j+1], and either s[k-1] or s[k+1] exists and is equal to f[j]. We first move from position i to either position k-1 or position k+1, whichever is equal to f[j], using the second kind of move, and then to position k using the first kind of move (so we will write down f[j+1]). The cost c is the sum of costs of the two moves. We need to be careful when both positions k-1 and k+1 contain f[j] and take the one that is closer.

The time complexity is \mathcal O(n^2 m). The problem can be solved in \mathcal O(nm) complexity, but that is left as an exercise to the reader.


Comments

There are no comments at the moment.