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

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

\begin{document}

\renewcommand{\problemName}{Задача Подкуп 2}

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

Ето няколко възможни идеи за решение:

\subsection{MST}
Просто да намерим максимално покриващо дърво с Крускал -- това би дало около 20 точки.

\subsection{Редуване на тегла}
Да редуваме малки и големи тегла в Крускал -- това би дало около 33 точки. 

\subsection{Hill Climb}
Доста използван подход за output-only задачи. Първоначално нека минималното покриващо ни е със сума $min$, а максималното с $max$. Една идея за решение е да вземем някакво покриващо дърво (попринцип има значение дали ще е минимално, максимално или случайно такова, но всичко е добре да се пробва), и да почнем да правим hill climb по него. На всяка итерация, избираме някакво случайно ребро, което махаме и избираме ребро, което свърза двете нови компоненти. Стремим се дървото да има сума $min+0.67(max-min)$. Подобна стратегия, използвайки максимално покриващо дърво, би дала малко точки -- авторските решения получават около 9 точки. Друг вариант е като начално покриващо дърво да използваме намереното от следващата подзадача, но се оказва, че това всъщност го \textbf{отдалечава} от отговора, получавайки около 47 точки.

\subsection{Симулация с произволни покриващи дървета}
Директно да направим това, което ни казват в условието, с някакъв избран от нас брой случайни покриващи дървета. Това решение работи много добре, и взима много точки (около 75) с не много голям брой покриващи дървета ($\frac{10^8}{N}$).

Предпочитаме да не разглеждаме пълни решения, тъй като се оказва, че използват FFT и динамично програмиране, така че около 85 точки са достатъчни \emoji{slightly-smiling-face}

\end{document}
