\documentclass[12pt]{article} 
\input{ejoi_structure_analysis.tex}

\usepackage[bulgarian]{babel}
\usepackage{emoji}

\begin{document}

\renewcommand{\problemName}{Задача Майнкрафт}

\section{Анализ на задача minecraft}
\begin{center}
	Решение, идея: Димитър Шапатов; Условие, анализ: Кирил Зашев
\end{center}

\subsection{Първи етап}
Нека разгледаме два начина да решим първия етап:
\begin{itemize}
	\item Divide and conquer: нека в момента искаме да намерим позициите на всички портали в интервала $[l,r]$. Разделяме интервала на две равни части, и пускаме divide and conquer за двете половини. Ако някой интервал има брой портали, равен на дължината му, директно взимаме позициите на порталите и спираме.
	\item Двоично търсене: броя портали за всеки префикс по нарастване на дължината му е монотонно. Така можем да намерим порталите само със заявки с $l=1$. Този подход средно използва два пъти повече заявки и носи около 93 точки.  
\end{itemize}

\subsection{Втори етап}
Ако не сте разбрали какво се търси -- имаме начални върхове (порталите в случая) и искаме да намерим най-краткото разстояние от някой начален връх до друг краен град (адските крепости) в граф. 

Нека разгледаме две възможни решения:
\begin{itemize}
	\item Бавно решение: пускаме Дийкстра от всеки начален връх и взимаме неговото минимално разстояние до някой краен град.
	\item Бързо решение: вкарваме всички начални върхове в приоритетната опашка преди да почнем Дийкстра. Първоначалното разстояние до всеки начален връх е 0, а всички начални върхове се обработват едновременно и това е аргумент, с който можем да докажем коректността на тази Дийкстра.
\end{itemize}

\subsection{Трети етап}
Нека разгледаме две възможни решения:
\begin{itemize}
	\item Бавно решение: обикаляме всяка двойка координати, докато не попаднем на NONE.
	\item Бързо решение: правим двумерно двоично търсене. Ще трябва да се поддържат по две показалки за интервалът на search space -- една за първото имерение и друга за второто измерение.
\end{itemize}

\end{document}
