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

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

\begin{document}

\renewcommand{\problemName}{Задача Езици}

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

\subsection{Подзадача 1}
Тази подзадача е по-дълга, тъй като първоначално беше самостоятелна. Накратко условието е да разделим $N$ агенти на две групи така, че във всяка група да няма недоверие между двама агенти, тоест да няма ребро между двама, при което $t=0$.

На практика задачата е чисто имплементационна. В авторовото решение е предложен подход с DFS, който
последователно посещава върхове и им дава "цвят". Този цвят всъщност ни казва в коя група трябва да се намира дадент агент.

Това означава, че когато има връзка между два върха при $t=1$, то тези върхове трябва да са един цвят, а ако $t=0$ трябва да са различен. 

Ако от даден връх може да стигнем до друг, който вече е оцветен, тогава правим следното - намираме кой трябва да е новия цвят на посетения връх и ако не съвпада със стария, това означава, че не е възможно да разделим агентите на две групи. В противен случай продължаваме обикалянето, като се съобразяваме да не пускаме DFS от вече посетен връх.

Решение с DSU (Митко):

Можем да представим всеки агент като два върха -- един, където е в първата група и един, където е във втората.

Когато двама агенти си доверяват, ги свързваме в двете групи.
Когато двама агенти не си доверяват, свързваме първата група на първия агент с втората група на втория агент и обратно.

Накрая ако двете групи на някой агент са свързани, това означава, че за да удовлетвори условието трябва да е и в двете групи, следователно се получава противоречие.

\subsection{Подзадача 2}
Задачата е да се намери максимална дълбочина на дърво. 

\subsection{Подзадача 3}
Задачата е да се намери разликата между максимално и минимално число в редица. 

\subsection{Подзадача 4}
Задачата е да се намери броя на двойките $i < j$, където $a_i+a_j$ е четно. Можем да преброим броя четни числа и броя нечетни, след което отговорът ни е $\frac{odd*(odd-1)}{2}+\frac{even*(even-1)}{2}$, понеже четно+четно=четно, нечетно+нечетно=четно.

\subsection{Подзадача 5}
Задачата е да се намери броя на четни числа в редица.

\subsection{Подзадача 6}
Задачата е да се намери броя числа, които са строго по-големи от всички преди тях.

\subsection{Подзадача 7}
Задачата е да се намери броя различни числа в редицата.

\subsection{Подзадача 8}
Задачата е да се намери някоя непразна подредица със сума, която се дели на $N$ без остатък. Тази задача е по-сложна идейно в сравнение с миналите. Има доказателство, че за всяка редица има валидно решение, което е последователен подмасив. Ако разгледаме префиксните суми по модул $N$, то искаме да намерим две еднакви стойности. Доказателството е, че префиксите имат $N+1$ позиции (включваме празния префикс), а само $N$ валидни стойности, следователно поне една стойност се среща поне два пъти.

\subsection{Подзадача 9}
Задачата е да се намери максимална сума на последователен подмасив, което можем да направим, като поддържаме текущия префикс и минималната сума на префикс до този момент.

\subsection{Подзадача 10}
Задачата е да се намери XOR на редицата. 

\end{document}
