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 $a$ 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. 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.
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 interpretata 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 medie, clasele 11-12)
Problema se rezolva prin metoda programarii dinamice. Fie {@M[j][i][r]@} numarul de moduri de a alege subsiruri +distincte+ de lungime $j$ din primele $i$ cifre ale numarului {$N$}, subsiruri care sa dea restul $r$ la impartirea {$K$}. Daca ne aflam in starea {$(j, i, r)$} putem sa actualizam starea {$(j+1, first[cif][i+1], (r*10+cif) mod K)$}, considerand ca am adaugat la sfarsitul fiecarui subsir definit de {$(j, i, r)$} cifra {$cif$}. Prin {$first[cif][i]$} se defineste prima aparitie in numarul $N$ a cifrei $cif$ dupa pozitia {$i$}. Tabloul $first$ va fi, evident, preprocesat. Pentru a numara subsirurile +distincte+ ( adica sa nu numaram subsiruri egale de doua ori ), daca suntem in starea {$(j, i, r)$} actualizam starea {$(j+1, first[cif][i+1], (r*10+cif) mod K)$} daca si numai daca intre pozitiile $i+1$ si $first[cif][i+1]-1$ in numarul $N$ nu mai apare nici o cifra {$cif$}. Acest lucru poate fi deasemenea calculat prin preprocesare, inainte de a incepe algoritmul de programare dinamica.
Problema se rezolva prin metoda programarii dinamice. Fie {$M[j][i]{@[r]@}$} numarul de moduri de a alege subsiruri distincte de lungime $j$ care contin ca ultima cifra cea de-a $i$-a cifra a numarului {$N$}, subsiruri care sa dea restul $r$ la impartirea {$K$}. Daca ne aflam in starea {$(j, i, r)$} putem sa actualizam starea {$(j+1, first[cif][i+1], (r*10+cif) mod K)$}, considerand ca am adaugat la sfarsitul fiecarui subsir definit de {$(j, i, r)$} cifra {$cif$}. Prin {$first[cif][i]$} se defineste prima aparitie in numarul $N$ a cifrei $cif$ dupa pozitia {$i$}. Tabloul $first$ va fi, evident, preprocesat. Pentru a nu numara subsirurile egale de doua ori, trebuie sa initializam pentru lungimea 1 doar pozitiile care contin pentru prima oara o cifra. Astfel initializam starile {$(1, @first[cif][0]@, cif mod K)$} cu 1, pentru cif = 1..9 (ca nu cumva un subsir sa inceapa cu 0). Pe parcurs, adunam la solutie starile care au lungimea cuprinsa intre $A$ si $B$ si care au $r$ egal cu 0.
Complexitatea finala a algoritmului este {$O(K * L^2^)$}, unde L este numarul de cifre ale numarului {$N$}.
h2. Radiatie
h3. (problema grea, clasele 11-12)
h3. (problemă 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 în rezolvarea problemei este construirea arborelui parţial de cost minim a grafului dat în {$O(M*logM)$}, folosind unul din algoritmii clasici precum Kruskal sau Prim. Se poate demonstra că o interogare în graful iniţial este echivalentă cu o interogare în arborele parţial minim.
Pentru a determina cea mai mare valoare a unei muchii pe drumul unic din arbore între nodurile $i$ şi $j$ procedăm astfel: pentru orice nod $i$ din arbore şi pentru orice $j$, fie {$A[i][j]$} = al {$2^j^$}-lea stramos al nodului $i$ in drumul spre radacină (aleasă aleator la început) şi {$B[i][j]$} = muchia de cost maxim dintre cei {$2^j^$} strămoşi ai nodului {$i$}. Precalculând aceste matrice în {$O(N*logN)$} se poate răspunde la un query în {$O(log N)$}, mergând înspre rădăcină simultan din $x$ şi $y$ pe strămoşi pe baza puterilor lui 2 până când întâlnim primul nod care este strămoş al ambelor noduri. La fiecare pas vom actualiza răspunsul prin compararea cu valorea elementelor corespunzătoare din tabloul $B$.
O soluţie şi mai simplă de implementat este folosirea arborelui care rezultă în urma algoritmului lui Kruskal, renunţând la euristica de compresie a drumului, şi folosind doar euristica după rang. Se poate demonstra că o interogare în arborele parţial minim este echivalentă cu o interogare în arborele de mulţimi disjuncte obţinut din algoritmul lui Kruskal. Cum acest arbore are înălţimea {$O(logN)$}, se poate folosi o parcurgere trivială pentru a răspunde la orice query.
==Include(page="template/preoni-2007/footer")==
