\documentclass[12pt]{article}
\usepackage[T2A]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage[russian]{babel}
\usepackage{amsthm, amsmath, amssymb}
\usepackage[russian]{hyperref}
\usepackage{datetime}
\usepackage{cmap}
\usepackage{hologo}
\usepackage{enumerate}
\usepackage{picture}

\voffset=-20mm
\textheight=220mm

\hoffset=-20mm
\textwidth=175mm

\def\EPS{\varepsilon}
\def\SO{\Rightarrow}
\def\EQ{\Leftrightarrow}
\def\t{\texttt}
\def\O{\mathcal{O}}

\newcommand\Label[1]{\item {\bf #1}}
\def\Begin{$\bullet$\hspace{0.5em}}

\newenvironment{MyList}{
  \begin{enumerate}[1.]
  \setlength{\parskip}{-5pt}
  \setlength{\itemsep}{5pt}
}{
  \end{enumerate}
}

\begin{document}

\begin{center}
  {\Large \bf Какая-то лекция по алгоритмам} \\ 
  \vspace{0.5em}
  {\Large \bf Тема: 3 задачки на динамику} \\
  \vspace{0.5em}
  {\Large Когда-то там} \\
  \vspace{0.5em}
  {Собрано {\today} в {\currenttime}}
\end{center}

\vspace{-1em}
\noindent \underline{\hbox to 1\textwidth{{ } \hfil{ } \hfil{ } }}

\vspace{1em}
\tableofcontents
\pagebreak

\section{Задача 1(Билет 12)}

\begin{itemize}
  \setlength{\parskip}{-5pt}
  \setlength{\itemsep}{8pt}
  \Label{Формулировка}: Из порта нужно увезти груз из $n$ ящиков. Все ящики стоят в ряд, и каждый ящик имеет вес $w_i$. Требуется увезти все грузы, используя минимальное число перевозок, на корабле грузоподъёмности $W$, если в любой момент времени разрешается грузить только самый левый или самый правый ящик
  \Label{Решение 1}: \\
    \Begin Динимика : $d_{lr}$ - минимальное число поездок, которое потребуется, чтобы увезти все грузы, кроме $[l, r)$  \\
    \Begin База : $d_{0n} = 0$ \\
    \Begin Переход  : $d_{lr} \rightarrow d_{(l+x)(r-y)}$ (погрузили на корабль $x$ ящиков слева и $y$ ящиков справа)\\
    \Begin Итог : состояний $O(n^2)$, переходов $O(n^2)$ Общее время работы $O(n^5)$ или $O(n^4)$, если использовать частичные суммы
  \Label{Улучшение решения 1}: \\
  \Begin Заметим, что если мы погрузили на корабль $x$ ящиков слева, то нам всегода выгодно погрузить как можно больше ящиков справа. Максимальный $y$ можно быстро находить, используя метод двух указателей \\
  \Begin Итог : переходов стало $O(n)$. Общее время работы $O(n^3)$
  \Label{Решение 2}: \\
  \Begin Динимика : $d_{lrf}$ - минимальный вес, который нужно положить на корабль при $(f+1)$-ой погрузке, чтобы в порту остались грузы $[l, r)$ и было сделано $f$ перевозок \\
    \Begin База : $d_{0n0} = 0$ \\
    \Begin Переход  : \\
    \begin{MyList}
    \item $d_{lrf} \rightarrow d_{(l+1)rf}$ (погрузили на корабль левый ящик) \\
    \item $d_{lrf} \rightarrow d_{l(r+1)f}$ (погрузили на корабль правый ящик) \\
    \item $d_{lrf} \rightarrow d_{lr(f+1)}$ (отправили корабль) \\
    \end{MyList}
    \Begin Итог : состояний $O(n^3)$, переходов $O(1)$ Общее время работы $O(n^3)$.
    \Label{Решение 3}: \\
  \Begin Динимика : $d_{lr}$ - минимальная пара $<f, w>$, где $f$ - число поездок, а $w$ - вес, загруженный на корабль для $(f+1)$-ой поездки\\
    \Begin База : $d_{0n} = <0, 0>$ \\
    \Begin Переход  : \\
    \begin{MyList}
    \item $d_{lr} \rightarrow d_{(l+1)r}$ (погрузили на корабль левый ящик) \\
    \item $d_{lr} \rightarrow d_{l(r+1)}$ (погрузили на корабль правый ящик) \\
    \end{MyList}
    \Begin Итог : состояний $O(n^2)$, переходов $O(1)$ Общее время работы $O(n^2)$.
    \Label{Поговорим о памяти}\\
    \Begin В наивном написании решения 3 будет использовано $O(n^2)$ памяти\\
    \Begin Будем считать динамику в порядке увеличения $l$, тогда нам достаточно хранить два массива для $l$ и $l + 1 \Rightarrow O(n)$ памяти\\
    \Begin Если требуется восстановить ответ, сделаем это алгоритмом Хиршберга\\
\end{itemize}

\section{Задача 2(В билетах нет, можно не читать)}

\begin{itemize}
  \setlength{\parskip}{-5pt}
  \setlength{\itemsep}{8pt}
  \Label{Формулировка}: Есть квадратная доска $N \times N$. У каждой клетки есть стоимость прохождения $w_{ij}$. Требуется за минимальную цену добраться из левого нижнего угла в правый верхний, если можно двигаться влево, вправо и вверх на одну клетку
  \Label{Решение}: \\
    \Begin Динимика : $d_{xy}$ минимальная цена, которая потребуется, чтобы добраться из левого нижнего угла в клетку $[x, y]$ \\
    \Begin База : $d_{00} = w_{00}$ \\
    \Begin Переход : пересчитывать динамику будем сразу для всей строки. Для этого достаточно сделать два цикла : слева направо и справа налево\\
    \Begin Память : для данного алгоритма достаточно хранить две последние строки $\Rightarrow O(n)$ памяти, но теперь, если мы попытаемся восстеновить ответ алгоритмом Хиршберга, время работы увеличится с $O(n ^ 2)$ до $O(n^2\log n)$. В качестве альтернативы, можно хранить $\sqrt n$ строк на расстоянии $\sqrt n$, а между ними честно считать ответ, тогда время работы останется $O(n^2)$, а памяти потребуется $O(n\sqrt n)$
\end{itemize}

\section{Задача 3(В билетах нет, можно не читать)}

\begin{itemize}
  \setlength{\parskip}{-5pt}
  \setlength{\itemsep}{8pt}
  \Label{Формулировка}: На плоскости расположены красные и сние точки. Требуется найти наибольший по площади выпуклый многоугольник на красных точках, внутри которого нет синих точек
  \Label{Решение}: \\
  	\Begin Переберём нижнюю вершину многоугольника и отсортируем вершины выше по углу. Теперь найдём ответ для многоугольника с текущей нижней вершиной\\
    \Begin Динимика : $s_{ij}$ - максимальная площадь многоугольника, удовлетворяющего условию, и в котором вершины с номерами $i$ и $j$ в порядке увеличения угла являются последней и предпоследней соответственно\\
    \Begin База : $s_{12} = S_{\bigtriangleup(0, 1, 2)}$ \\
    \Begin Переход : $s_{ij} = \max_{k}(s_{ki} + S_{\bigtriangleup(0, i, j)})$  Нужно проверить, что многоугольник остался выпуклым, и что в добавляемом треугольнике нет синих точек (это можно предподсчитать для всех треугольников)\\
    \Begin Итог : перебираем все вершины за $O(n)$, $O(n^2)$ состояний динимики и $O(n)$ переходов. Получаем общее время работы алгоритмя $O(n^4)$
\end{itemize}

\end{document}
