Diferente pentru preoni-2007/runda-1/solutii intre reviziile #16 si #33

Nu exista diferente intre titluri.

Diferente intre continut:

==Include(page="template/preoni-2007")==
h1. Runda 1
 
* avertisment inregistrare
* cometarii despre clasament
h1. Solutii Runda 1
h2. Aprindere
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 exista intra $a$ si $b$ este suficient sa facem o operatie AND pe biti intre grupurile corespunzatoare de biti si sa aflam cati biti de 1 contine acest numar.
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, 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(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.
 
 
h2. 1-sir
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 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 î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")==

Diferente intre securitate:

private
public

Topicul de forum nu a fost schimbat.