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

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$ 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. Pe parcurs, adunam la solutie starile care au lungimea cuprinsa intre $A$ si $B$ si care au $r$ egal cu 0.

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

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")==