\Section{Кучи и динамика}{23 октября}{Олег Свидченко}

\Subsection {Кучи. Две оптимизации куч}

\begin{MyList}

\item{\bf Оптимизация операции Add}\\

{\bf Формулировка}

Пусть есть куча, которая кмеет делать $Add$, $Merge$ и $ExtractMin$ за $O(\log(n))$ действий и $Build$ за $O(n)$ действий. Хотим из нее сделать кучу, которая делает $Merge$ и $ExtractMin$ за $O(\log(n))$ действий, $Add$ за $O(1)$ действий и $Build$ за $O(n)$ действий.\\

{\bf Идея решения}

Буферезированный $Add$.\\

{\bf Описание решения}

Когда делаем $Add$, добавляем элемент в $buffer$. Когда делаем остальные операции, сначала делаем $Build(buffer)$ и $Merge$ результата с кучей, а потом саму операцию.\\

{\bf Реализация (псевдокод)}
\begin{code}
struct Q
    vector buffer;
    Heap heap;

Add(x)
    buffer.pop_back(x);

Merge(q)
    heap.Merge(Build(buffer));
    q.heap.Merge(Build(q.buffer));
    heap.Merge(q.heap);

ExtractMin()
    heap.Merge(Build(buffer));
    return heap.ExtractMin();

Build(vect)
    heap.Build(vect);
\end{code}

{\bf Доказательство асимптотики}

Интуитивное:\\
Равномерно распределим действия, которые делает $Build$, между сделанными операциями $Add$. Тогда $Add$ все еще делает $O(1)$ действий, а операции $Merge$ и $ExtractMin$ делают $O(\log(n))$ действий.\\

Строгое (метод потенциалов):\\
Пусть $\phi$ равно количеству $k$ элементов в $buffer$, умноженному на константу $c$ (нужно, чтобы можно было сократить $O(k)$, которое делает $Build$ с $\delta\phi$). Тогда:\\
$Add$: $\delta\phi = c$; $t_{i} = O(1)$ $\Rightarrow$ $a_{i} = O(1)$\\
$Merge$: $\delta\phi = - c \cdot k$; $t_{i} = O(k) + O(\log(n))$ $\Rightarrow$ $a_{i} = O(\log(n))$\\
$ExtractMin$: $\delta\phi = - c \cdot k$; $t_{i} = O(k) + O(\log(n))$ $\Rightarrow$ $a_{i} = O(\log(n))$

Доказательство корректно, т.к. $0 \leq \phi_{i} \leq c \cdot n$;\\\\

\item{\bf  Оптимизация Merge}\\

{\bf Формулировка}

Пусть есть куча, которая умеет делать $ExtractMin$ и $Merge$ за время $O(\log(n))$, $Add$ за время $O(1)$ и $Build$ за время $O(n)$. Хотим сделать из нее кучу, которая умеет делать $ExtractMin$ за время $O(\log(n))$, $Add$ и $Merge$ за время $O(1)$ и $Build$ за время $O(n)$. 

{\bf Идея решения}

На основе старой кучи типа $Q$ создать новую кучу типа $B$, которая хранит минимум и кучу $Q$ куч $B$\\

{\bf Описание решения}

Куча типа $B$ содержит поля $min$ (минимальный эдемент) и $q$ (куча типа $Q$ куч типа $B$)\\

\begin{Def}
$b_{1} < b_{2} \Leftrightarrow b_{1}.min < b_{2}.min$, где $b_{1}$ и $b_{2}$ - кучи типа $B$.
\end{Def}

$Add$ - это создание кучи типа $B$, состоящей из минимума, равного добавляемому элементу, и пустой кучи типа $Q$ и добавление ее в $q$. ($q.Add$)

$Merge$ - пусть $b_{1} < b_{2}$. Тогда Merge этих куч добавит в $b_{1}.q$ кучу $b_{2}$. ($b_{1}.q.Add$)

$ExtractMin$ - возвращает значение поля min на момент начала своего выполнения. Нужно получить новый минимум. Очевидно, что он хранится в $b_{tmp} = q.ExtractMin()$ (см. определение сравнения двух куч типа $B$). Теперь $min = b_{tmp}.min$, $q = Merge(q, b_{tmp})$.

$Build$ - $Add$, сделанный $n$ раз. \\

{\bf Реализация (псевдокод)}

\begin{code}
template <class T>
struct B
    T min;
    Q< B<T>* >* q;


//Add == Merge

void Merge(B* b1, B* b2)
    if(b1->min > b2->min)
        swap(b1,b2);
    b1->q->Add(b2); //O(1)


T ExtractMin(B* b)
    T result = b->min;
    B* btmp = b->q->ExtractMin(); //O(log(n))
    b->min = btmp->min;
    b->q = QMerge(b2->q,b->q) //Merge two Q-type heaps. Q. Not B.
    return result;

\end{code}

\end{MyList}

\Subsection{Динамическое программирование и перемножение матриц. Быстрое возведение в степень.}

{\bf Задача про подсчет путей из $a$ в $b$ длины $k$}\\

{\bf Формулировка}

Дан ориентированный граф и таблица смежности $is_edge[a][b]$. Посчитать количество путей из вершины $a$ в вершину $b$ длины ровно $k$.\\

{\bf Решение}

Динамика. Состояния: длина пути $k$, начальная вершина $a$, конечная вершина $b$.

Переход:

$f[k][a][b] = \sum\limits_{c}(f[k-1][a][c] \cdot is_edge[c][b])$\\

Заметим, что это то же самое, что и $f[k] = f[k-1] \cdot is_edge$, где $f[k]$, $f[k-1]$ и $is_edge$ - матрицы.

($C = A \cdot B \Leftrightarrow C_{i;j} = \sum\limits_{k}(A_{i;k} \cdot B_{j;k})$)

$\Rightarrow f[k] = f[0] \cdot is_edge^{k} = is_edge^{k}$\\

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

Изначально динамика работала за $O(n^{3} \cdot k)$. Теперь работает $O(n^{3} \cdot \log(k))$ (используем быстрое возведение в степень).\\

{\bf Быстрое возведение в степень}

\begin{code}
Pow(A,n)
    if(n == 0)
        return E;
    x = Pos(A, n / 2);
    x = x*x;
    if(n % 2 == 1)
        x = x*A;
    return x;
\end{code}

{\bf Задача про числа Фибоначчи}\\

{\bf Формулировка}

Посчитать $n$-ное число Фибоначчи.\\

{\bf Решение}

$\begin{pmatrix} F_{n} \\ F_{n-1} \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} \cdot \begin{pmatrix} F_{n-1} \\ F_{n-2} \end{pmatrix}$

$\begin{pmatrix} F_{n} \\ F_{n-1} \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^{n-1} \cdot \begin{pmatrix} F_{1} \\ F_{0} \end{pmatrix}$