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

h2. 1-sir
h3. (problema usoara, clasele 11-12)

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.

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.

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