h3. (problema usoara, clasa a 10-a)

Putem considera cele $N$ animale ca fiind noduri ale unui graf neorientat si o relatie de forma $i j$ ca fiind muchie intre nodurile $i$ si {$j$}. Problema cere determinarea numarului de triunghiuri in graful astfel construit ( numarul de triplete de noduri astfel incat intre oricare doua noduri din triplet exista muchie ). O solutie imediata are complexitatea {$O(N^3^)$}, prin generarea tuturor tripletelor. O solutie mai buna se bazeaza pe urmatorul rationament: pentru fiecare muchie din graf $a b$ trebuie sa vedem cate noduri adiacente cu $a$ si $b$ exista in graf ( adica cate triunghiuri care contin nodurile $a$ si $b$ se pot forma ). Pentru o muchie fixata este suficienta iterarea prin lista de adiacenta a nodurilor $a$ si $b$ si adunarea la numarul total de solutii a numarului de noduri comune. Acest algoritm are complexitatea {$O(M * N)$}, pentru ca parcurgerea unei liste de adiacenta se realizeaza in $O(N)$. Algoritmul de mai sus poate fi optimizat prin tinerea pe grupuri de biti a listei de adiacenta. Astfel, pentru orice nod {$i$}, primii $B$ biti din lista lui de adiacenta vor reprezenta legaturile cu primele $B$ noduri din cele {$N$} ( bit 1 pentru legatura si 0 altfel ), urmatorii $B$ biti legaturile cu nodurile $B+1...2*B$, etc. Pentru a vedea cate noduri adiacente comune au $a$ si $b$ este suficient sa realizam o operatie AND intre grupurile corespunzatoare de biti si sa adunam la numarul total de solutii numarul de biti de 1 din acest numar. Complexitatea acestui algoritm este {$O(M*N/B)$}, unde $B$ este numarul de biti dintr-un grup.

Putem considera cele $N$ animale ca fiind noduri ale unui graf neorientat si o relatie de forma $i j$ ca fiind muchie intre nodurile $i$ si {$j$}. Problema cere determinarea numarului de triunghiuri in graful astfel construit ( numarul de triplete de noduri astfel incat intre oricare doua noduri din triplet exista muchie ). O solutie imediata are complexitatea {$O(N^3^)$}, prin generarea tuturor tripletelor. O solutie mai buna se bazeaza pe urmatorul rationament: pentru fiecare muchie din graf $a b$ trebuie sa vedem cate noduri adiacente cu $a$ si $b$ exista in graf ( adica cate triunghiuri care contin nodurile $a$ si $b$ se pot forma ). Pentru o muchie fixata este suficienta iterarea prin lista de adiacenta a nodurilor $a$ si $b$ si adunarea la numarul total de solutii a numarului de noduri comune. Acest algoritm are complexitatea {$O(M * N)$}, pentru ca parcurgerea unei liste de adiacenta se realizeaza in $O(N)$. Algoritmul de mai sus poate fi optimizat prin tinerea pe grupuri de biti a listei de adiacenta. Astfel, pentru orice nod {$i$}, primii $B$ biti din lista lui de adiacenta vor reprezenta legaturile cu primele $B$ noduri din cele {$N$} ( bit 1 pentru legatura si 0 altfel ), urmatorii $B$ biti legaturile cu nodurile $B+1...2*B$, etc. Pentru a vedea cate noduri adiacente comune au $a$ si $b$ este suficient sa realizam o operatie AND intre grupurile corespunzatoare de biti din listele de adiacenta ale lui $a$ si ale lui $b$ si sa adunam la numarul total de solutii numarul de biti de 1 din acest numar. Complexitatea acestui algoritm este {$O(M*N/B)$}, unde $B$ este numarul de biti dintr-un grup.

h2. Pachete

h3. (problema grea, clasele 11-12)

Primul pas in rezolvarea problemei este construirea arborelui partial de cost minim a grafului dat in O(M*log~2~M), folosind unul din algoritmii clasici precum Kruskal sau Prim. Se poate demonstra ca  o interogare in graful initial este echivalenta cu o interogare in arborele partial minim. Pentru a determina cea mai mare valoare a unei muchii pe drumul unic din arbore intre nodurile $i$ si $j$ procedam astfel: pentru orice nod $i$ din arbore si pentru orice $j$, fie {$A[i][j]$} = al {$2^j^$}-lea stramos al nodului $i$ in drumul spre radacina ( aleasa aleator la inceput ) si {$B[i ][j]$} = muchia de cost maxim dintre cei {$2^j^$} stramosi ai nodului {$i$}. Precalculand aceste matrici in {$O(N*log~2~ N)$} se poate raspunde la un query in {$O(log^2^ N)$}, mergand inspre radacina simultan din $x$ si $y$ pe stramosi pe baza puterilor lui 2 pana cand intalnim primul nod care este stramos al ambelor noduri. La fiecare pas vom actualiza raspunsul prin compararea cu valorea elementelor corespunzatoare din tabloul $B$.
O solutie si mai simpla de implementat este folosirea arborelui care rezulta in urma algoritmului lui Kruskal, renuntand la euristica de compresie a drumului, si folosind doar euristica dupa rang. Se poate demonstra ca o interogare in arborele partial minim este echivalenta cu o interogare in arborele de multimi disjuncte obtinut din algoritmul lui Kruskal. Cum acest arbore are inaltimea medie {$O(log~2~N)$}, se poate folosi o parcurgere triviala pentru a raspunde la orice query.

==Include(page="template/preoni-2007/footer")==