Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2007-02-18 16:10:31.
Revizia anterioară   Revizia următoare  

Solutii Runda 1

Aprindere

(problema usoara, clasa a 9-a)

Este evident ca nu are rost sa actionam un intrerupator de mai multe ori. In aceste conditii, solutia este unica, deoarece nu putem avea doua intrerupatoare intr-o singura camera. Cu alte cuvinte, daca parcurgem camerele de la stanga la dreapta si intalnim o camera cu becul inchis, va trebui sa actionam intrerupatorul unic din camera respectiva. Daca am fi permis ca o camera sa aiba mai multe intrerupatoare, problema s-ar fi complicat semnificativ.
Se pot afla usor intrerupatoarele care trebuie actionate astfel: se parcurg camerele de la stanga la dreapta, iar in momentul in care ajungem la o camera cu becul inchis trebuie sa actionam intrerupatorul din camera respectiva (daca nu exista intrerupator, atunci nu avem solutie). Cum intrerupatorul respectiv actioneaza becuri din camere ≥ i, nu vom modifica nimic din becurile precedente. De asemenea, vom aduna costul lor la rezultat.

Patrate3

(problema medie, clasa a 9-a)

Mai intai sortam punctele crescator dupa abscisa, iar pentru abscise egale dupa ordonata. Acum, folosind cautarea binara putem cauta orice punct in timp logaritmic. Pentru fiecare pereche de puncte vom forma patratul care are o diagonala formata din perechea respectiva. Dupa ce calculam si celelalte 2 puncte, le cautam binar in vectorul sortat. Daca le gasim, inseamna ca am mai gasit un patrat. Complexitatea solutiei este O(N2 log N). Precizia recomandata este de 10-4.
Singura problema care ramane de rezolvat acum e calcularea punctelor patratului daca stim doar o diagonala. O metoda simpla de gasire a lor, ce nu necesita cunostiinte avansate de geometrie, este observarea simetriilor care se formeaza fata de centrul patratului. Fie x0, y0 si x1, y1 coordonatele diagonalei cunoscute iar x2, y2 si x3, y3 coordonatele necunoscute. Centrul patratului este mijlocul unei diagonale, deci coordonatele lui sunt mijx = (x0 + x1) / 2 si mijy = (y0 + y1) / 2. Sa notam dx = abs(mijx - x0) si dy = abs(mijy - y0). Se observa ca daca y0 < y1 atunci x2 = mijx + dy, y2 = mijy - dx, x3 = mijx - dy iar y3 = mijy + dx. In caz contrar, avem x2 = mijx - dy, y2 = mijy - dx, x3 = mijx + dy iar y3 = mijy + dx.

Elimin

(problema grea, clasa a 9-a / problema medie, clasa a 10-a)

Daca S este suprafata ( aria ) matricii, este evident ca minim(M, N) ≤ sqrt(S). Pentru primele 3 teste se observa ca cel putin o dimensiune este ≤ 10. Pentru celelalte teste avem:

  • 266 = 2 * 7 * 19
  • 539 = 7 * 7 * 11
  • 1630 = 2 * 5 * 163
  • 3495 = 3 * 5 * 233
  • 3653 = 13 * 281
  • 5866 = 2 * 7 * 419
  • 7294 = 2 * 7 * 521

Se observa ca in toate cazurile de mai sus, oricum am grupa numerele prime pentru a obtine dimensiunile matricii, cea mai mica dintre dimensiuni nu poate depasi 15. Deci, in toate testele, stim sigur ca min(M, N) ≤ 15. Sa presupunem ca aceasta dimensiune este numarul coloanelor, N, celalalt caz rezolvandu-se identic, rotind matricea.
Putem genera toate posibilitatile de a elimina exact C coloane din numarul total de N. Pentru fiecare caz generat, calculam suma elementelor ramase pentru fiecare linie in parte, si sortam aceste sume. Evident, vom elimina cele mai mici R sume.
Complexitatea unui astfel de algoritm este deci O(2N * (M log M + M*N)).

Triplete

(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(N3), 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.

Pachete

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

1-sir

(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(N3) si obtine punctajul maxim.

Diviz

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

Complexitatea finala a algoritmului este O(K * L2), unde L este numarul de cifre ale numarului N.

Radiatie

(problema 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 2j-lea stramos al nodului i in drumul spre radacina ( aleasa aleator la inceput ) si B[i][j] = muchia de cost maxim dintre cei 2j 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.

Sponsori

Organizarea finalei preONI este posibila datorita generosilor nostri sponsori: