\begin{tutorial}{Подарок Уэнсдей}

\textit{Автор задачи и разработчик: Олег Сметанкин}
\vspace{0.2em}


При рассмотрении второго примера из условия можно понять, что простое жадное решение не будет работать.
Поэтому для решения задачи используем динамическое программирование. Начнем с базовой идеи и оптимизируем ее.
Можно сделать динамику, в которой мы последовательно идём по строке $s$ и решаем к какой из строк приписать текущий символ.
Тогда сделаем состояние ДП из трех значений: количество рассмотренных символов в строке $s$ ($c_s$), количество символов,
которые были дописаны к $t_1$ ($c_{t1}$) и количество символов, которые были дописаны к $t_2$ ($c_{t2}$). Асимптотика решения
будет $O(n \cdot |t_1| \cdot |t_2|)$ по времени и памяти, что слишком много. 

Заметим, что можно избавиться от последнего параметра, 
потому что $c_{t2} = c_s - c_{t1}$. Тогда асимптотика получится $O(n \cdot |t_1|)$ по времени и памяти. По времени решение
уже проходит, но нужно уменьшить асимптотику по памяти. Так как по строке $s$ мы идем последовательно, нам важны лишь состояния
на текущем и прошлом рассмотренных символах для обновления ДП. Поэтому первый параметр $c_s$ можно сделать неявным, для этого
просто храним состояния на прошлом символе $s$ и через них обновляем состояния на текущем символе. После полного пересчета для текущего символа
можно записать текущее состояние в прошлое. Получится асимптотика $O(n \cdot |t_1|)$ по времени и $O(|t_1|)$ по памяти.

\end{tutorial}
