\section{Задача <<Древние династии>>}

\begin{frame}[t]{Задача <<Древние династии>>}

  \begin{center}
    \LARGE Задача <<Древние династии>>
  \end{center}

\end{frame}

\begin{frame}[t]{Задача <<Древние династии>>}

  \begin{center}
    \LARGE Задача <<Древние династии>>
  \end{center}

  \begin{itemize}
    \item Идея задачи --- Глеб Евстропов
    \item Подготовка тестов --- Глеб Евстропов, Михаил Пядёркин
    \item Разбор задачи --- Михаил Пядёркин
  \end{itemize}
\end{frame}

\subsection{Формулировка задачи}

\begin{frame}[t]{Математическая формулировка}
	\begin{itemize}
		\item На прямой отмечено $n$ различных точек.
		\item Необходимо покрасить их в два цвета (белый и черный) так, чтобы для каждой точки ближайшая точка того же цвета находилась
		      на расстоянии в пределах от $[l_i,r_i]$.
		\item Требуется минимизировать количество пар соседних точек одного цвета
	\end{itemize}
	\begin{center}
		\includegraphics[height=50px]{dynpic1.png}
	\end{center}
\end{frame}

\subsection{Решение}

\begin{frame}[t]{Простое решение первой подзадачи}
	\begin{itemize}
		\item Будем перебирать все возможные варианты покраски точек (всего $2^n$ вариантов).
		\item Для каждого варианта нетрудно проверить, является ли он корректным.
		\item Среди корректных необходимо выбрать тот, который минимизирует искомую величину
		\item 20 баллов
	\end{itemize}
	\begin{center}
		\includegraphics[height=50px]{dynpic1.png}
	\end{center}
\end{frame}

\begin{frame}[t]{Динамическое программирование}
	\begin{itemize}
		\item Необходимо знать лишь те моменты, в которые в последний раз встречался тот или иной цвет
		\item Пусть $ans_{i,j}$ обозначает минимальное количество пар соседних точек одного цвета в корректной раскраске 
		отрезка $[1,max(i,j)]$, где $i$ --- последний момент, когда точка была окрашена в белый цвет, $j$ --- последняя точка,
		окрашенная в черный цвет
	\end{itemize}
	\begin{center}
		\includegraphics[height=35px]{dynpic3.png}
	\end{center}
\end{frame}

\begin{frame}[t]{Переход}
	\begin{itemize} 
		\item Переход: будем выбирать, в какой именно цвет стоит покрасить элемент $max(i,j)+1$.
		\item Допустим, мы хотим покрасить её в черный цвет. Необходимо проверить, что $x_{max(i, j) + 1} - x_j$ лежит в пределах
		$[l_1,r_1]$, после этого попробовать обновить ответ для состояния $ans_{i,max(i, j) + 1}$.
		\item $O(n^2)$ состояний, $O(n^2)$ переходов, $O(n^2)$ памяти, 40 баллов
	\end{itemize}
	\begin{center}
		\includegraphics[height=30px]{dynpic3.png}
	\end{center}
\end{frame}

\begin{frame}[t]{Другое динамическое программирование}
	\begin{itemize}
		\item Выберем в качестве состояния момент последний момент смены цвета 
		\item Будем перебирать, где произошла последняя смена состояния цвета ранее этого состояния
		\item Проверим, что новый покрашенный отрезок действительно можно покрасить (между соседними точками отрезка
		подходящие для данного цвета расстояния), и что можно прыгнуть в предыдущую точку из нашей
	\end{itemize}
	\begin{center}
		\includegraphics[height=30px]{dynpic2.png}
	\end{center}
\end{frame}

\begin{frame}[t]{Оптимизация перехода}
	\begin{itemize}
		\item $O(n)$ состояний, $O(n^2)$ переходов, каждый переход за $O(n)$, $O(n)$ памяти
		\item Итоговое время работы $O(n^3)$, 20 баллов
		\item Перебирая переходы справа налево, можно проверять отрезок на корректность по ходу
		\item $O(1)$ на один переход, итоговое время работы $O(n^2)$, $O(n)$ памяти
		\item 60 баллов
	\end{itemize}
\end{frame}

\begin{frame}[t]{Непрерывные отрезки}
	\begin{itemize}
		\item Задача равносильна максимизации количества пар точек разного цвета
		\item Допустимые клетки, в которые мы можем перейти из текущей, представляют собой непрерывный отрезок
		\item На этом отрезке необходимо выбирать максимум
		\item Используя дерево интервалов, получаем $\log n$ на один переход, итоговое время работы $O(n \log n)$ и 80 баллов
	\end{itemize}
\end{frame}

\begin{frame}[t]{Непрерывные отрезки и сдвиг}
	\begin{itemize}
		\item При переходе к следующему состоянию, границы допустимого отрезка двигаются только вправо
		\item Границы этого отрезка можно поддерживать с помощью метода двух указателей
		\item Для отрезка, который двигается вправо (<<окно>>) мы можем решать задачу о поиске максимума за $O(n)$ в сумме
	\end{itemize}
\end{frame}

\begin{frame}[t]{Минимум в <<окне>>}
	\begin{itemize}
    	\item Для этого будем поддерживать \texttt{deque}, в котором будем держать текущих кандидатов для максимума.
    	\item При добавлении
    	элемента в конец (сдвиге правой границы) будем выбрасывать элементы с конца, пока они меньше текущего. 
    	\item При сдвиге
    	левой границы просто выбрасываем элемент с начала (если он там есть)
    	\item $O(n)$ и заслуженные 100 баллов.
  \end{itemize}
\end{frame}

\begin{frame}
  \begin{center}
    {\LARGE Вопросы?}
  \end{center}
\end{frame}
