\section{Задача J. <<Супрематизм>>}

\begin{frame}[t]{Задача J. <<Супрематизм>>}

  \begin{center}
    \LARGE Задача J. <<Супрематизм>>
  \end{center}

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

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


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

\begin{frame}[t]{Постановка задачи}
    \begin{wrapfigure}{r}{0.25\textwidth}
        \begin{center}
            \includegraphics[width=0.25\textwidth]{pics/supreme-1.png}
        \end{center}
    \end{wrapfigure}

    Входные данные:

    \begin{itemize}
        \item Таблица из $n \times m$ чисел (\emph{цветов} клеток).
        \item Можно перекрашивать строку в цвет $c$, если в ней более, чем
            $\left\lfloor\frac{m}2\right\rfloor$ клеток цвета $c$.
        \item Аналогично, столбец~--- если в нём больше 
            $\left\lfloor\frac{n}2\right\rfloor$ клеток цвета $c$.
    \end{itemize}
    Нужно раскрасить всю таблицу в один цвет или сказать, что это сделать 
    нельзя.
\end{frame}

\subsection{Решение}

\begin{frame}[t]{Важное наблюдение}
Если ответ есть, то есть ответ, в котором все перекрашивания происходят в один
цвет.
\pause
\begin{itemize}
    \item Допустим, что это не так.
    \pause
    \item В конце таблица полностью раскрашена в цвет $c$.
    \item Индукция по числу $r$ раскрашиваний в цвета, отличные от $c$:
        \begin{itemize}
            \item $r = 0$~--- ничего делать не надо.
            \item $r > 0$. Последнее перекрашивание в цвет $c' \ne c$.
                Если бы его не было, всё равно можно было бы докрасить.
        \end{itemize}
\end{itemize}
\end{frame}

\begin{frame}[t]{Цвета-кандидаты}
\begin{columns}
    \begin{column}{0.6\textwidth}
        \begin{itemize}
            \item Если в цвет в начальной таблице нельзя раскрасить ни один 
                столбец и ни одну строку, то и всю таблицу в него нельзя 
                раскрасить.
            \item \emph{Цвета-кандидаты}~--- цвета, в которые можно раскрасить 
                хотя бы одну строку или столбец.
                \begin{itemize}
                    \item Их не более $n + m$.
                \end{itemize}
        \end{itemize}
    \end{column}
    \begin{column}{0.4\textwidth}
        \includegraphics[width=\textwidth]{pics/supreme-3.png}
    \end{column}
\end{columns}
\end{frame}

\begin{frame}[t]{Почему не хватит одного цвета?}
    \begin{center}
        \includegraphics[width=3.5cm]{pics/supreme-4.png}
    \end{center}
    \begin{itemize}
        \item Рассматривать только цвет, которого больше всего, нельзя (WA12).
        \item На этой картинке больше всего центрального цвета, однако, в него
            раскрасить нельзя.
        \item А в два других можно.
    \end{itemize}
\end{frame}

\begin{frame}[t]{Решение}
    \begin{itemize}
        \item Переберём всех кандидатов.
        \item Проверим, можно ли раскрасить в этот цвет $c$ всё поле.
        \pause
        \begin{itemize}
            \item Для каждой строки и каждого столбца будем считать
                сколько там элементов цвета $c$.
            \pause
            \item Пробежимся по всем строкам, если в ней от
                $\left\lfloor\frac{m}2\right\rfloor+1$ до $m-1$ элементов цвета
                $c$, то пробежимся по ней, перекрашивая не-$c$ в $c$ и
                пересчитывая количества.
            \item Аналогично для столбцов.
        \end{itemize}
    \end{itemize}
\end{frame}

\begin{frame}[t]{Сложность}
\begin{itemize}
    \item Каждая строка и каждый столбец перекрашиваются не более
        одного раза. 
    \item Перекрашивание происходит за $O(n)$ или $O(m)$.
    \item Нахождение очередной цели для перекрашивания~--- 
        $O(n+m)$.
    \item Итого, проверка того, можно ли покрасить в данный 
        цвет~--- $O((n+m)^2)$.
    \item Всего цветов для проверки~--- $n+m$. Итоговая сложность~---
        $O((n+m)^3)$.
\end{itemize}
\end{frame}

%\begin{frame}[t]{Решение за $O(n^2)$}
%\begin{itemize}
%    \item Можно рассматривать три самых популярных цвета и пытаться красить
%        только в них.
%        \pause
%        \begin{itemize}
%            \item Без доказательства :(
%        \end{itemize}
%        \pause
%    \item Каждый из них можно, как и раньше проверить за $O(n^2)$.
%\end{itemize}
%\end{frame}
