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 ith position in the scary word, and we want to write down the jth 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[k1] or s[k+1] exists and is equal to f[j]. We first move from position i to either position k1 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 k1 and k+1 contain f[j] and take the one that is closer.

The time complexity is O(n2m). The problem can be solved in O(nm) complexity, but that is left as an exercise to the reader.


Comments

There are no comments at the moment.