% !TEX program = lualatex % (can also use "xelatex") 
\documentclass[12pt]{article}
\input{ejoi_structure.tex}

\usepackage[bulgarian]{babel}
    
\begin{document}

\renewcommand{\round}{Ден 0}
\renewcommand{\problemName}{Задача Дърво}
\renewcommand{\lang}{Български}

\renewcommand{\tl}{$1.0$ sec.}
\renewcommand{\ml}{$256$ MB} 
\problem{\problemName}
Алиса си е намислила дърво с $N$ върха и ще го превърне в низ от нули и единици. Тя ще играе с Боби, който ще се опита да възстанови дървото от този низ, като преди това те са се разбрали за стратегията, която ще използват. Вашата цел е да имплементирате стратегия за двамата, която използва низове с минимална дължина.

\subsection{Детайли по имплементацията}
Трябва да имплементирате следните функции, които ще бъдат извикани в \textbf{отделни} процеси:
\begin{lstlisting}
std::string encode(int N, std::vector<std::pair<int, int>> v);
\end{lstlisting}
Тази функция реализира стратегията на Алиса. Тя се извиква веднъж от журито и като параметър се подават броят върхове и двупосочните ребра $(x,y)$, описващи дървото. Трябва да върне низ от нули и единици с минимална дължина, описващ дървото.
\begin{lstlisting}
std::vector<std::pair<int, int>> decode(int N, std::string s);
\end{lstlisting}
Тази функция реализира стратегията на Боби. Тя се извиква веднъж от журито и като параметър се подават броят върхове и низът на Алиса. Трябва да върне оригиналното дърво, описано с двупосочни ребра $(x,y)$. Няма значение редът на ребрата, както и на върховете в тях.

\subsection{Ограничения}
\begin{itemize}
\item $3 \leq N \leq 10^5$
\end{itemize}

\subsection{Оценяване}
Нека $S$ е дължината на низа на Алиса. Тогава $points=\min((\frac{(N-1)(\left \lfloor{\log_2 N}\right \rfloor + 1)}{S})^2, 1)$.

\subsection{Пример}
\begin{table}[H]
\begin{tblr}{|Q[c,m]|Q[c,m]|}
\hline
\textbf{Жури} & \textbf{Състезател}\\
\hline
\texttt{encode(3, \{\{1, 2\}, \{2, 3\}\})} & \texttt{"1000011"}\\
\hline
\texttt{decode(3, "1000011")} & \texttt{\{\{1, 2\}, \{2, 3\}\}}\\
\hline
\end{tblr}
\end{table}
Това решение получава $(\frac{2 \cdot 2}{7})^2\approx32.7\%$ от точките на дадения тест.

\subsection{Примерен грейдър}
На първия ред се въвежда числото $N$. На следващите $N-1$ реда се въвеждат ребрата $(x, y)$.

\end{document}


