O parte din problemele date in cadrul acestui concurs (cele propuse de Mugurel Ionut Andreica) au fost folosite pentru a selecta echipele care au reprezentat Universitatea Politehnica Bucuresti la etapa regionala sud-est europeana a concursului ACM ICPC, in anul 2006.

(toc)*{text-align:center} *Lista de probleme*
* 'AVD':happy-coding-2006/solutii#nr1
 

h2. 'AVD':problema/avd
Cea mai simpla solutie consta in generarea tuturor submultimilor de muchii pe care le eliminam. Ce ramane este o reuniune de componente conexe, care defineste fiecare cate o partitie. Dintre toate cele $2^N-1^$ partitii generate, le pastram pe cele unice si impartim acest numar la numarul total de partitii (care poate fi generat si el prin backtracking sau folosind programare dinamica).
O solutie mai laborioasa consta in generarea fiecarei partitii (putin peste $100$, pt $N=13$) si, pentru fiecare astfel de partitie (care are, sa presupunem $K$ elemente), calcularea urmatoarelor valori: $ok[i][j][S] = 1$ sau $0$ , reprezentand daca e posibil sau nu sa se "acopere" elementele partitiei corespunzatoare starii $S$ ( $S$ e un numar pe $K$ biti), folosind nodurile din subarborele lui $i$ si ramanand $j$ noduri, inclusiv nodul $i$, intr-o componenta conexa pe care nu o "potrivim" peste vreun element al partitiei (si care poate fi eventual extinsa ulterior de catre un stramos al lui $i$); o valoare $j=0$ indica ca au fost folosite toate nodurile din subarborele lui $i$, inclusiv $i$, pentru a genera componente conexe care se "potrivesc" peste elemente ale partitiei. Aceste valori se calculeaza folosind programare dinamica de tip rucsac pe arbore, in functie de valorile calculate pentru fii (valori de tipul $ok[fiu][j'][S']$, cu $j' < j$ si $S'$ inclus in $S$). Daca $ok[ 1 ][ 0 ][2^K^-1]$ are valoarea $1$, atunci se poate genera o impartire in componente conexe a arborelui, ce corespunde partitiei respective.

h2(#nr1). 'CT':problema/ct

h2. 'CT':problema/ct

Se fixeaza radacina arborelui intr-un nod (sa zicem nodul $1$). Pentru fiecare din cele $K$ perechi de orase se calculeaza $LCA$-ul (lowest common ancestor = cel mai apropiat stramos comun). Se poate folosi orice metoda eficienta de determinarea a $LCA$-ului: de exemplu, pentru fiecare nod $i$ se pot memora $O(logN)$ valori, $stramos[i][j]$, reprezentand stramosul aflat cu $2^j^$ nivele mai sus in arbore (cu $j$ incepand de la $0$), iar cu aceste valori, $LCA$-ul a oricare $2$ noduri se poate determina in timp $O(logN)$. Se sorteaza apoi $LCA$-urile tuturor perechilor, in functie de nivelul din arbore ({$LCA$}-urile de pe un nivel mai jos aflandu-se inaintea celor de pe un nivel mai ridicat). In continuare, vom parcurge $LCA$-urile in ordinea sortata. Pentru a rezolva problema, avem acum $2$ posibilitati: