\Section{Матрицы и динамика}{23 октября}{Богомолов}
\Subsection{Еще немножко о матрицах}
\begin{MyList}

\item{\bf Постановка задачи:}\\

Последовательность задана рекуррентным соотношением такого вида:\\ 

$F_n = \sum\limits_{i=1}^k C_i F_{n-i} + b$\\

Элементы \{$F_1 \dots F_k$\} даны. Требуется вычислить элемент послеовательности с номером N.

\item{\bf Решение для случая $b = 0$ :} 

Запишем переход от элементов \{$F_n \dots F_{n-k+1}$\} к \{$F_{n+1} \dots F_{n-k}$\} как домножение вектора на матрицу:

$$
\begin{pmatrix}F_{n + 1} \\ F_n \\ F_{n-1} \\ \cdots \\ F_{n-k} \end{pmatrix} =\begin{pmatrix}C_1 & C_2 & \dots & C_{k-1} & C_k \\ 1 & 0 & \dots & 0 & 0 \\ 0 & 1 & \dots & 0 & 0 \\ \cdots & \cdots & \cdots  & \cdots & \cdots \\ 0 & 0 & \dots & 1 & 0 \end{pmatrix} \cdot \begin{pmatrix}F_n \\ F_{n-1} \\ F_{n-2} \\ \cdots \\ F_{n-k+1} \end{pmatrix} = M \cdot V
$$\\

Домножением первой строки матрицы на вектор получим элемент $F_{n+1}$ в точности так, как он задан в соотношении. Следующие строки перенесут соответствующие элементы $F_n \dots F_{n-k}$ в новый вектор. 

Запишем формулу для получения вектора, содержащего элемент с номером N:\\

$ \{ F_{N-k+1} \dots F_N \} =  \{ F_1 \dots F_k\} \cdot M^{N-k}$\\

\item{\bf Случай $b \neq 0$ :}

Немного дополним матрицу и заметим, что все замечательно работает:

$$
\begin{pmatrix}F_{n + 1} \\ F_n \\ \cdots \\ F_{n-k} \\ 1 \end{pmatrix} =\begin{pmatrix}C_1 & C_2 & \dots & C_k & b \\ 1 & 0 & \dots & 0 & 0 \\ \cdots & \cdots & \cdots  & \cdots & \cdots \\ 0 & 0 & \dots & 1 & 0 \\ 0 & 0 & \dots & 0 & 1 \end{pmatrix} \cdot \begin{pmatrix}F_n \\ F_{n-1} \\ \cdots \\ F_{n-k+1}  \\ 1 \end{pmatrix} = M \cdot V
$$\\

Теперь в первой строчке в сумму добавляется $b$, остальные строки все так же переносят соответствующие элементы $V$ и единицу.

\item{\bf Время работы:}

Матрица имеет размер $k \times k$, умножение происходит за $O(k^3)$. Используя быстрое возведение в степень, получаем время $O(k^3 \log N)$.

\end{MyList}	

\Subsection{Задача о министерствах}

\begin{MyList}

\item{\bf Постановка задачи:}\\

Дана прямоугольная матрица ($n \times m$), для каждой клетки известна стоимость ее посещения $cost_{i,j} \geq 0$. Изначально вы стоите в первой строке, в клетке с координатами (1 ; s). Нужно найти путь минимальной стоимости в клетку (n ; t). Разрешается ходить в клетку, соседнюю по стороне, кроме клетки в предыдущей строке.

\item{\bf Полезные наблюдения:}\\

Существует оптимальный ответ, в котором каждая клетка будет посещена не более 1 раза.

Рассмотрим какой-нибудь оптимальный ответ. Возьмем в нем клетку, посещенную более одного раза. Удалим все переходы от ее первого до последнего вхождения в ответ. Ответ не ухудшился, так как мы вычли сумму неотрицательных чисел. Размер ответа уменьшился. Так как он конечный, за конечное число итераций сможем построить из любого оптимального ответа такой, в котором все клетки посещены не более 1 раза. 

\item{\bf Решение задачи:}\\

Будем считать такую динамику: $dp_{i,j}$ -- минимальная стоимость, за которую можно добраться до клетки (i ; j). Пересчитывать ее будем по строкам. 

Для очередной строки $i$ сделаем два пробега -- слева направо и справа налево. В первом случае будем релаксировать $dp_{i,j}$ переходом из $dp_{i,j-1}$, во втором -- переходом из $dp_{i,j+1}$. Так как посещать одну клетку более одного раза бессмысленно (см. выше), все возможные пути, проходящие по этой строке тем самым обработаны. Перейдем в строку $i + 1$. Для этого значение в каждой клетке строки $i + 1$ прорелаксируем переходом в нее из предыдущей строки. Итого, обработка строки затрачивает $O(m)$ времени.

Если не нужно восстанавливать ответ, то можно хранить значение динамики только в последних двух строках. Тогда получаем решение, затрачивающее $O(m)$ памяти и $O(nm)$ времени.

\item{\bf Восстановление ответа:}\\

Самый простой вариант -- для каждой клетки хранить ее предка. Но такое решение будет использовать $O(nm)$ памяти, давайте улучшим:

\begin{MyList}

\item{\bf Делим и властвуем:}\\

Разделим строки на две половины (верх/низ). В каждой из них посчитаем динамику с линейной памятью, найдя при этом для каждой клетки из центральной строки предка из первой строки, а для клеток из последней -- предка из центральной (аналогично алгоритму Хиршберга). Так найдем часть центральной строки, которая войдет в ответ. Ее можно хранить сжато (координаты клетки, в которой входим в центральную строку, и координаты клетки, в которой выходим). Затем вызовемся рекурсивно от каждой из половин, склеим их ответы с помощью посчитанного в центральной строке.

Память стала линейной - на каждом уровне рекурсии тратим $O(m)$ памяти на динамику, затем оставляем $O(1)$ на ответ для центральной строки. Но при этом время ухудшилось до $O(nm\log n)$, так как теперь каждая строка будет участвовать в пересчете динамики $\log n$ раз.

\item{\bf Обобщим этот метод:}\\

В предыдущем пункте мы поделили таблицу на две части, а что, если поделим на $k$? Как теперь будет работать динамика: делим строки на k групп, в каждой группе считаем динамику, поддерживая массив предков из последней строки предыдущей группы. Вызываемся рекурсивно от каждой группы, склеиваем полученные ответы.

Теперь затраченная память -- $O(km)$. Каждая строка теперь будет участвовать в динамике $\log_k n$ раз, итоговое время $O(nm \log_k n)$.

\item{\bf Примеры выбора k:}\\

\begin{itemize}

\item{Если хранили всех предком, мы делили доску на n строк:}

$Mem = O(nm)$

$Time = O(nm \log_n n) = O(nm)$\\


\item{Если делили на 2 группы:}

$Mem = O(2nm) = O(nm)$

 $Time = O(nm \log_2 n)$\\

\item{Если поделим на  $\sqrt n$:}

 $Mem = O(nm \sqrt n)$

$Time = O(nm \log_{\sqrt n} n) = O(nm)$\\

\end{itemize}
\end{MyList}

\item{\bf Немножко выводов:}

Алгоритм Хиршберга был применим только в задачах, где переходы из состояния (i, j) были в (i + 1, j), (i, j + 1) и (i + 1, j + 1). Описанный в этой задач метод восстановления ответа позволяет работать с еще двумя типами переходов -- в (i, j - 1) и (i + 1, j - 1), это здорово.

\end{MyList}
