Solutii Concursul Mihai Patrascu 2013

• Lista de probleme
• Album
• Rectangles
• Treemis

Album

Solutie:

1. Sortam jucatorii fiecarei echipe: O(N K log K).
2. Construim graful astfel: Fixam oricare doua echipe si comparam jucatorii in perechi. Daca toti jucatorii unei echipe sunt mai inalti decat corespondentii lor adaugam un arc de la echipa mai inalta la cea mai scunda. Graful e tranzitiv si antisimetric. O(N² K).
3. Transformam graful precedent in unul bipartit cu 2N noduri si facem cuplaj pentru a determina acoperirea minima cu lanturi.

Rectangles

Solutie:

1. Calculam toate punctele de intersectie intre doua dreptunghiuri si le adaugam intr-un set ca sa eliminam duplicatele.
2. Sortam punctele de intersectie dupa x si, separat, dupa y. Pentru fiecare punct calculam v[i][j] = cat de departe se intinde o linie continua din punctul i in directia j (nord, vest, sud, est).
3. Parcurgem punctele de intersectie pe diagonale (sa presupunem ca o diagonala e parcursa in ordinea sud-vest -> nord-est). Cand intalnim un punct nou, el are o perioada pentru care poate fi coltul stanga jos al unui patrat, perioada fiind data de min(v[i][nord], v[i][est]). Astfel avem doua tipuri de evenimente: (a) cand intalnim un punct nou si acesta poate fi coltul stanga-jos al unui patrat si (b) momentul in care acest punct nu mai poate fi coltul stanga-jos al unui patrat. In plus, cand intalnim un punct nou vrem sa numaram cate patrate putem forma daca acest punct reprezinta coltul dreapta-sus. Acest rezultat poate fi obtinut cu un query pe un AIB in functie de min(v[i][sud], v[i][vest]).
Complexitatea finala este O(N² * logN).

Treemis

Solutia 1 – O(N * log²N)

Rezolvam urmatorul caz particular al problemei: avand un arbore cu radacina fixata X, vrem sa vedem subsirul crescator maximal care merge “in jos” in arbore. Putem calcula si subsirul descrescator maximal in mod analog.
Pentru fiecare subarbore, calculam o stiva in care pe pozitia i se afla valoarea minima cu care se termina un subsir crescator maximal de lungime i. Astfel, cand vrem sa calculam stiva pentru arborele curent, vom uni stivele subarborilor fiecarui fiu. In noua stiva, pe pozitia i vom avea min(stiva[fiu][i]), dupa care cautam binar care e subsirul de lungime maxima pe care il poate extinde radacina arborelui si actualizam stiva. Daca folosim principiul de la heavy-path decomposition, acest lucru se poate realiza in timp O(N * logN) si memorie O(N).

Apoi generalizam cazul precedent: avand un arbore cu radacina fixata X, vrem sa vedem subsirul crescator maximal care trece prin radacina. Daca vom calcula stivele corespunzatoare fiilor, nu trebuie decat sa combinam un subsir crescator dintr-un subarbore cu un subsir descrescator din alt subarbore. Folosind cautare binara, acest lucru se poate realiza tot in O(N * logN).

Intrucat putem rezolva cele doua subprobleme, vom aborda problema initiala cu divide et impera. Alegem un nod X din arbore, fixam radacina arborelui in X si calculam subsirul crescator maximal care trece prin radacina X. Observam ca orice alt subsir care ar putea fi solutie nu va mai trece prin nodul X, astfel il putem sterge din arbore si sa rezolvam independent fiecare componenta conexa ramasa.
Daca atunci cand fixam radacina alegem tot timpul centrul de greutate al arborelui (nodul pentru care se obtine dimensiunea maxima a unei componente conexe minima dupa stergerea lui), complexitatea totala a problemei va fi de O(N * log²N).

Mai exista si o solutie in complexitate O(N * logN).