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