\section{Задача G. <<Осенний парк>>}

\begin{frame}[t]{Задача G. <<Осенний парк>>}

  \begin{center}
    \LARGE Задача G. <<Осенний парк>>
  \end{center}

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

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

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

\begin{frame}[t]{Постановка задачи}
Дано поле $n \times m$ с препятствиями.
Нужно вычислить количество путей из одной точки в другую, которые отличаются по длине от кратчайшего на два.
\end{frame}

\subsection{Решение}

\begin{frame}[t]{Нахождение количества кратчайших путей}
\begin{itemize}
	\uncover<1->%
	{%
	\item Запустим BFS из стартовой точки. Пусть ответ будет храниться в массиве $cnt$.
    \item А длины кратчайших путей будут в массиве $d$. \\
	}%
	\uncover<2->%
	{%
	\item Пусть вытащили на очередном шаге вершину $v$.
	}%
	\uncover<3->%
	{%
	\item Мы пробегаем по всем её соседям. Пусть рассматриваем сейчас соседа $u$. 
    \item Если расстояние до $u$ больше чем расстояние до $v$, то $cnt[u] = (cnt[u] + cnt[v]) \mod 10^9+9$. \\
	}%
\end{itemize}
\end{frame}

\begin{frame}[t]{Подправление алгоритма}%
\begin{itemize}
    \uncover<1->{
    \item Добавляем для вершины $v$ вершину $v'$, в которой будут заканчиваться пути
      длиннее кратчайшего на 2.
    }
    \uncover<2->{
    \item Добавим ребро из $v$ в $u'$, если было ребро из $v$ в $u$ и $d[v] = d[u] + 1$.
    }
    \uncover<3->{
    \item Таким образом, применяя алгоритм для количества кратчайших путей, мы находим ответ.
    }
\end{itemize}
\end{frame}

