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 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.

Exista si o solutie $O(N)$ pentru aceasta problema. Stim ca numarul maxim de triunghiuri din graf este $N*(N-1)*(N-2)/6$. Vom scadea din acest numar cate triplete $(a b c)$ de noduri exista care nu sunt triunghiuri. Stiind gradul fiecarui nod, numarul de triplete care nu sunt triunghiuri si contin nodul $nod$ este $grad[nod]*(N-1-grad[nod])$, fiindca putem construi un triplet cu nodul $nod$, un nod adiacent, si unul neadiacent.

h2. Pachete
h3. (problema grea, clasa a 10-a)

Sa consideram initial ca oficiul postal este in punctul de coordonate {$(0, 0)$} si restul oraselor au coordonate pozitive ( sunt toate in primul cadran ). Se sorteaza orasele dupa abscisa {$X$}. Dupa sortare, acestea trebuie partitionate intr-un numar minim de subsiruri astfel incat intr-un subsir coordonatele punctelor ({$Y$}) sa fie crescatoare. Un astfel de subsir reprezinta drumul unui postas (este de cost minim deoarece mereu merge in dreapta si in sus). Algoritmul optim pentru aflarea numarului minim de subsiruri crescatoare in care poate fi partitionat un sir are complexitatea {$O(Nlog{~2~}N)$}. Primul element va face parte din primul subsir. La pasul {$i$}, {$i>1$}, elementul al $i$-lea va fi introdus in acel subsir care se termina intr-un element cu valoare mai mica decat elementul curent si care are valoarea maxima dintre toate elementele de acest tip. Cautarea se poate face cu o cautare binara in raport cu ultimele pozitii pentru fiecare subsir, pentru ca se observa ca printr-un astfel de procedeu ultimile valori vor fi intotdeauna sortate descrescator.

Sa consideram initial ca oficiul postal este in punctul de coordonate {$(0, 0)$} si restul oraselor au coordonate pozitive ( sunt toate in primul cadran ). Se sorteaza orasele dupa abscisa {$X$}. Dupa sortare, acestea trebuie partitionate intr-un numar minim de subsiruri astfel incat intr-un subsir coordonatele punctelor ({$Y$}) sa fie crescatoare. Un astfel de subsir reprezinta drumul unui postas (este de cost minim deoarece mereu merge in dreapta si in sus). Algoritmul optim pentru aflarea numarului minim de subsiruri crescatoare in care poate fi partitionat un sir are complexitatea {$O(NlogN)$}. Primul element va face parte din primul subsir. La pasul {$i$}, {$i>1$}, elementul al $i$-lea va fi introdus in acel subsir care se termina intr-un element cu valoare mai mica decat elementul curent si care are valoarea maxima dintre toate elementele de acest tip. Cautarea se poate face cu o cautare binara in raport cu ultimele pozitii pentru fiecare subsir, pentru ca se observa ca printr-un astfel de procedeu ultimile valori vor fi intotdeauna sortate descrescator.

Daca oficiul postal se afla in {$(Px, Py)$}, acest punct imparte planul in {$4$} cadrane, si se aplica aceeasi rezolvare de mai sus pentru fiecare cadran.

h3. (problema usoara, clasele 11-12)

Prima observatie este aceea ca valoarea maxima pe care o poate lua $S$ este {$N * (N-1) / 2$}, sirul {$a$} fiind egal cu {$(0, 1, 2... N-1)$}, iar valoarea minima {${@-N * (N-1) / 2@}$}, caz in care sirul este egal cu {$(0, {@-1@}, {@-2@}... {@-(N-1)@})$}. Daca notam cu {$D[N][S]$} numarul de 1-siruri cu $N$ termeni care au suma elementelor $S$, atunci se observa ca {$D[N][S] = D[N-1][S-(N-1)] + D[N-1][S+(N-1)]$}, deoarece avem doua posibilitati de alegere pentru al doilea element (1 sau -1), si fiecare alegere poate fi interpreta ca o translatie pentru fiecare din elementele urmatoare cu 1 sau -1 ( deci in total o translatie in functie de suma de {$N-1$}, cu plus sau cu minus ). Pentru a evita folosirea indicilor negativi pentru suma este suficient sa observam ca {$D[N][S] = D[N][-S]$}, pentru orice {$S > 0$}, relatie evidenta din faptul ca se poate forma o bijectie intre 1-sirurile cu suma {$S$} si cele cu suma {${@-S@}$} printr-o simpla inmultire cu -1. Pentru ca algoritmul sa se incadreze in limita de memorie este suficient sa retinem doar ultimele doua linii din tabloul $D$. Un astfel de algoritm obtine punctajul maxim.

Prima observatie este aceea ca valoarea maxima pe care o poate lua $S$ este {$N * (N-1) / 2$}, sirul {$s$} fiind egal cu {$(0, 1, 2... N-1)$}, iar valoarea minima {${@-N * (N-1) / 2@}$}, caz in care sirul este egal cu {$(0, {@-1@}, {@-2@}... {@-(N-1)@})$}. Daca notam cu {$D[N][S]$} numarul de 1-siruri cu $N$ termeni care au suma elementelor $S$, atunci se observa ca {$D[N][S] = D[N-1][S-(N-1)] + D[N-1][S+(N-1)]$}, deoarece avem doua posibilitati de alegere pentru al doilea element (1 sau -1), si fiecare alegere poate fi interpreta ca o translatie pentru fiecare din elementele urmatoare cu 1 sau -1 ( deci in total o translatie in functie de suma de {$N-1$}, cu plus sau cu minus ). Pentru a evita folosirea indicilor negativi pentru suma este suficient sa observam ca {$D[N][S] = D[N][-S]$}, pentru orice {$S > 0$}, relatie evidenta din faptul ca se poate forma o bijectie intre 1-sirurile cu suma {$S$} si cele cu suma {${@-S@}$} printr-o simpla inmultire cu -1. Pentru ca algoritmul sa se incadreze in limita de memorie este suficient sa retinem doar ultimele doua linii din tabloul $D$. Un astfel de algoritm are complexitate $O(N^3^)$ si obtine punctajul maxim.

h2. Diviz

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 {$O(log{~2~}N)$}, se poate folosi o parcurgere triviala pentru a raspunde la orice query.

Primul pas in rezolvarea problemei este construirea arborelui partial de cost minim a grafului dat in {$O(M*logM)$}, 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*logN)$} se poate raspunde la un query in {$O(log 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 {$O(logN)$}, se poate folosi o parcurgere triviala pentru a raspunde la orice query.

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