\section{Задача I. <<Необычный экспонат>>}

\begin{frame}[t]{Задача I. <<Необычный экспонат>>}
  \begin{center}
    \LARGE Задача I. <<Необычный экспонат>>
  \end{center}

$$\includegraphics[width=8cm]{pics/scanner.jpg}$$
\end{frame}

\begin{frame}[t]{}
  \vspace{3cm}
  \begin{itemize}
    \item Идея задачи --- Артур Рязанов
    \item Подготовка тестов --- Демид Кучеренко
    \item Разбор задачи --- Виталик Аксёнов, Андрей Комаров
  \end{itemize}
\end{frame}

\subsection{Постановка задачи}

\begin{frame}[t]{Постановка задачи}
\begin{itemize}
    \item Даны количества инверсий на всех подотрезках длины $k$ перестановки чисел от $1$ до $n$.
    \item Нужно восстановить любую перестановку, удовлетворяющую условию.
    \item Гарантировалось, что всегда такая перестановка существует.
\end{itemize}
\end{frame}

\subsection{Решение}

\begin{frame}[t]{План решения}
\begin{itemize}
    \item Переберём, \emph{форму} какой перестановки имеют первые $k-1$ число
        ответа.
    \begin{itemize}
        \item Например, последовательность $\langle 100, 500, 239, 17\rangle$
            \emph{имеет форму} $\langle 2, 4, 3, 1\rangle$.
    \end{itemize}
    \item Попробуем построить подходящий под эту форму ответ.
\end{itemize}
\end{frame}

\begin{frame}[t]{Построения ответа по форме}
\begin{itemize}
    \item Пускай что-то известно про первые $m$ чисел (изначально, $m = k - 1$).
    \item Выясним что-нибудь про очередное число.
    \item Будем строить граф $G$. В $G$ есть ребро $i \to j$, если известно,
        что в строящемся массиве $a_i < a_j$.
    \item Про каждую пару из $\{a_{m-k+1}, a_{m-k+2}, \ldots, a_{m}\}$
        известно, какой элемент из пары максимальный.
    \item Перебрав $k$ вариантов того, как будет соотноситься с ними $a_{m+1}$,
        посчитаем количество инверсий на отрезке $a_{m-k+2..m+1}$ в каждом из
        этих случаев.
\end{itemize}
\end{frame}

\begin{frame}[t]{Восстановление ответа}
\begin{itemize}
    \item Получим нужное число инверсий не более, чем в одном из случаев.
    \begin{itemize} 
        \item Не получили ни в одном~--- переходим к следующей форме.
        \item Получили одно~--- переходим к следующему $m$.
    \end{itemize}
    \item По условию задачи хотя бы для одной формы дойдём до конца.
    \item Запустим алгоритм топологической сортировки на получившемся графе.
    \item Полученная перестановка и будет ответом.
\end{itemize}
\end{frame}
