(Categoria _Competitii_, autor(i) _Echipa Info-Arena_)

*Continut scurt:*
 ==Include(page="template/raw")==
 
Articolul contine ideile de rezolvare a problemelor cu care cei 29 finalisti preONI 2006 au avut ocazia sa se confrunte.
 
 
*Continut lung:*
==Include(page="template/raw")==
 

Si iata-ne ajunsi in situatia de a trage concluziile dupa tot ce a insemnat preONI 2006. Toata comisia infoArena merita felicitata pentru organizarea si efortul depus de-a lungul campaniei. Inca odata multimim domnului profesor Onea pentru organizarea "fara cusur" :).
Finala a fost ... "Super. Super", "Super tare", "mda...a mers" o spun concurentii. A fost grozav, intr-adevar, si ne-a facut mare placere sa va vedem prezenti intr-un numar atat de mare si veniti atat de departe. Va multumim pentru participare si speram ca ati petrecut un week-end pe cinste cu noi la Focsani.

Sa trecem la analiza problemelor cu care cei 29 concurenti nazdravani au avut de-a face in cele 5 ore ale finalei. Orice sugestie sau corectie privind articolul, solutiile problemelor v-o puteti exprima pe [2]forum.

 
 
DivK

h2. DivK

(problema usoara clasa a IX-a, problema usoara clasa a X-a)

Exista solutii evidente O(N * (A-B)) si O(N * K) care obtin punctaje partiale si asupra carora nu se va insista in acest articol. Solutia care obtine insa 100 de puncte este O(N) si nu este greu de gasit, bazandu-se pe cateva observatii. Sa notam cu S[i] suma primelor i numere din sir. Pentru ca subsecventa intre pozitiile i si j sa aiba suma elementelor divizibila cu K, atunci S[j]-S[i-1] trebuie sa fie divizibil cu K, sau altfel spus, S[i-1] si S[j] sa aiba acelasi rest la impartirea cu K. Daca stim sa aflam raspunsul problemei pentru subsecvente de lungime maxim L si minim 1, aplicand de doua ori algoritmul pentru B si pentru A-1 si scazand cele doua valori obtinute vom obtine numarul de subsecvente cu proprietatea ceruta intre A si B inclusiv. Pentru a afla raspunsul pentru lungimea maxim L procedam astfel: introducem in lista LISTA[r] alocata dinamic pozitiile i pentru care S[i] da restul r la impartirea cu K, in ordine crescatoare. Pentru fiecare rest de la 0 la K-1 parcurgem lista
corespunzatoarea, si, daca ne aflam pe un element cu valoarea p2 si elementul cel mai din stanga din lista curenta are valoarea p1 astfel incat p2-p1 <= L, atunci cand avansam in lista nu mai este necesar sa incepem iterarea listei de la inceput pentru aflarea valorii cea mai din stanga, fiind suficient sa reluam cautarea din dreptul valorii p1. Astfel complexitatea algoritmului pentru o lista este O(LUNGIME), unde LUNGIME este lungimea unei liste, deci complexitatea intregului algoritm va fi O(N), pentru ca lungimea tuturor listelor este N.
O alta solutie de aceeasi complexitate dar mai rapida este urmatoarea: daca notam cu v[r] de cate ori apare restul r in numerele S[i-B]...S[i-A+1] pentru pasul curent i, atunci la pasul i+1 este suficient sa decrementam v[S[i-B+1] % K] si sa incrementam v[S[i-A+2] % K]. La fiecare pas i vom aduna la solutia finala numarul v[S[i] % K].
 
 
 
Lupul Urias si Rau

Exista solutii evidente $O(N * (A-B))$ si $O(N * K)$ care obtin punctaje partiale si asupra carora nu se va insista in acest articol. Solutia care obtine insa $100$ de puncte este $O(N)$ si nu este greu de gasit, bazandu-se pe cateva observatii. Sa notam cu $S{~i~}$ suma primelor $i $numere din sir. Pentru ca subsecventa intre pozitiile $i$ si $j$ sa aiba suma elementelor divizibila cu $K$, atunci $S{~j~}-S{~i-1~}$ trebuie sa fie divizibil cu $K$, sau altfel spus, $S{~i-1~}$ si $S{~j~}$ sa aiba acelasi rest la impartirea cu $K$. Daca stim sa aflam raspunsul problemei pentru subsecvente de lungime maxim $L$ si minim $1$, aplicand de doua ori algoritmul pentru $B$ si pentru $A-1$ si scazand cele doua valori obtinute vom obtine numarul de subsecvente cu proprietatea ceruta intre $A$ si $B$ inclusiv. Pentru a afla raspunsul pentru lungimea maxim $L$ procedam astfel: introducem in lista $LISTA{~r~}$ alocata dinamic pozitiile $i$ pentru care $S{~i~}$ da restul $r$ la impartirea cu $K$, in ordine crescatoare. Pentru fiecare rest de la $0$ la $K-1$ parcurgem lista
corespunzatoarea, si, daca ne aflam pe un element cu valoarea $p2$ si elementul cel mai din stanga din lista curenta are valoarea $p1$ astfel incat $p2-p1 ≤ L$, atunci cand avansam in lista nu mai este necesar sa incepem iterarea listei de la inceput pentru aflarea valorii cea mai din stanga, fiind suficient sa reluam cautarea din dreptul valorii $p1$. Astfel complexitatea algoritmului pentru o lista este $O(LUNGIME)$, unde $LUNGIME$ este lungimea unei liste, deci complexitatea intregului algoritm va fi $O(N)$, pentru ca lungimea tuturor listelor este $N$.
O alta solutie de aceeasi complexitate dar mai rapida este urmatoarea: daca notam cu $v[r]$ de cate ori apare restul $r$ in numerele $S{~i-B~}...S{~i-A+1~}$ pentru pasul curent $i$, atunci la pasul $i+1$ este suficient sa decrementam $v[S{~i-B+1~} % K]$ si sa incrementam $v[S{~i-A+2~} % K]$. La fiecare pas $i$ vom aduna la solutia finala numarul $v[S{~i~} % K]$.
h2. Lupul Urias si Rau

(problema medie clasa a IX-a)
Se construieste vectorul T[i] care retine timpul maxim la care oaia i poate fi aleasa si notam T_max valoarea maxima din T.

O rezolvare ce aduce 100 de puncte se bazeaza pe metoda greedy. Pentru fiecare valoare j de la T_max la 1 se adauga intr-o multime toate cantitatile de lana A[i] pentru oile cu T[i]=j, apoi se extrage valoarea maxima care se adauga la solutie, restul valorilor pastrandu-se in multime pentru pasul urmator. Atentie, se va extrage valoarea maxima chiar daca la acest pas nu s-au introdus valori noi in multime. Pentru a implementa eficient aceste operatii ne vom folosi un heap care suporta operatiile de extragere maxim si adaugare element in O(log n). Complexitatea finala a algoritmului va fi de O(n log n). Demonstratia intuitiva a faptului ca algoritmul conduce la solutie optima este ca la fiecare pas j se alege valoarea maxima dintre cele care nu vor mai putea fi alese la pasul j+1.
O alta solutie tot greedy a problemei este sortarea descrescatoare dupa cantitatile de lana. Pentru fiecare valoare apoi se vede cel mai mare timp mai mic sau egal cu T[i] si la care nu a mai fost aleasa nici o alta oaie. Daca exista un astfel de timp se adauga valoare respectiva la solutie. Acest lucru se poate realiza cu o cautare binara a acestui timp. O alternativa la acest lucru ar fi folosirea multimilor disjuncte. Initial se considera fiecare moment de timp o multime. Notam X = minimul din multimea care il contine pe T[i]. Daca alegem A[i] pentru a-l aduaga la solutie se va reuni multimea care il contine pe X cu multimea care il contine pe X-1. Aceasta rezolvare insa este considerata peste nivelul mediu al clasei a 9-a.

 
 
Overlap
 

h2. Overlap

(problema grea clasa a IX-a)
Observam ca exista doar 4 rotatii posibile ale planului, facand abstractie de translatii. Daca CMAX este coordonata maxima, atunci punctul (i, j) se transforma in (CMAX-j, i), iar dupa 4 aplicari ale acestei transformari se ajunge din nou la punctul initial. Asadar, vom incerca pe rand fiecare dintre aceste posibilitati. Avand fixata o rotatie, stim ca punctul 1 se transforma intr-un alt punct i (i > 1), sau ca un punct i se transforma in el. Cel de-al doilea caz este redundant, deoarece aplicand transformarea P_i -> P_1, vom lua in considerare si transformarea inversa. De exemplu, daca rotind planul cu k*90 de grade si translatandu-l cu shift_X si shift_y obtinem P_i din P_j, atunci rotind planul cu (4-k)*90 grade si translatandu-l cu -shift_x, -shift_y vom obtine P_j din P_i.

Avand vectorul P, va exista o structura de lanturi si cicluri rezultata in urma aplicarii repetate P[P[..P[i]]] asupra diverselor puncte. Se poate demonstra usor ca exista solutie daca si numai daca toate lanturile si toate ciclurile au lungime para; in acest caz solutia se poate obtine etichetand alternativ punctele consecutive dintr-un lant sau ciclu.
Complexitatea algoritmului este O(N^2 * log N) pe cazul defavorabil folosind cautari binare pentru gasirea punctelor, sau O(N^2) pe cazul mediu folosind un hash (tabel de dispersie).

 
 
 
 
Iv
 

h2. Iv

(problema medie clasa a X-a)
Solutia simpla, calculata prin metoda programarii dinamice, se bazeaza pe mentinerea starilor ce asigura obtinerea solutiilor distincte. Astfel interclasarea celor doua siruri se va face in acelasi timp atat din stanga cat si din dreapta pentru a garanta pastrarea proprietatii de palindrom. Notand cele doua siruri A si B, pastram 4 indici: p1, p2, q1, q2, reprezentand pozitia ultimului caracter luat din stanga sirului A, ultimului luat din dreapta sirului A, ultimului din stanga sirului B, respectiv ultimului luat din dreapta sirului B.

Aceasta ne duce la un algoritm de complexitate O(|A|^2 * |B|^2), ce ar fi asigurat obtinerea a 60% din punctaj. Simpla observare a faptului ca este suficienta pastrarea a numai trei indici, in loc de patru, pentru a pastra o stare completa (deoarece p1 + p2 = |A| - q1 + 1 + |B| - q2 + 1), duce la un algoritm de complexitate O(|A|^2 * |B|) ce ar fi obtinut punctaj maxim.

 
 
Robotei
 

h2. Robotei

(problema grea clasa a X-a)
Pentru a afla de cate ori trece un robotel prin pozitia (X Y) avem nevoie de urmatoarele informatii:

Pornind din pozitia (X Y), efectuam o parcurgere BFS a grafului INVERSAT si vom afla, pentru fiecare nod, care este numarul de mutari pe care trebuie sa le efectuam, pornind din celula corespunzatoare nodului, pentru a ajunge in pozitia (X Y). Nodurile care nu pot fi vizitate in aceasta parcurgere corespund unor celule din care nu se poate atinge pozitia (X Y).
Complexitatea acestui algoritm este O(N*N) si obtine 70% din punctaj. Pentru a obtine punctaj maxim, observam ca, dupa prima mutare toti roboteii se afla in caroiajul de dimensiuni (modX modY), si aplicam acelasi algoritm ignorand pozitiile care sunt in afara acestuia. Observatia precedenta ne permite sa afirmam ca daca un robot pleaca din pozitia (i, j) e ca si cum ar pleca, imaginar, din pozitia (i modX, j modY). Putem determina cati roboti pleaca (considerandu-i si pe cei care pleaca imaginar) dintr-o celula (i j) a caroiajului redus, determinand cate solutii au ecuatiile x % modX = i si y % modY = j (x si y necunoscute) in intervalul [0..N-1].

 
 
PScNv
 

h2. PScNv

(problema simpla clasele XI-XII)
Aceasta problema a fost aleasa asa cum spune si textul pentru faptul ca sunt mai multe abordari ce rezolva problema. O prima abordare ar fi pentru un k fixat sa vedem daca putem ajunge de la nodul start pana la nodul destinatie folosind doar muchii cu cost mai mic sau egal cu k. Verificarea acestui fapt o facem folosind o cautare in latime. Cat timp nu putem ajunge de la nodul start la nodul destinatie incrementam pe k si apoi aplicam o cautare in latime. Astfel aflam valoarea k minima ceruta in problema. Complexitatea acestui algoritm este O(kmax (n + m)). Daca notam kmin valoarea ceruta in problema, atunci daca fixam un k si nodul destinatie este accesibil din nodul start folosind doar muchii de pondere mai mica sau egale cu k atunci este evident ca kmin <= k, iar daca nodul destinatie nu este accesibil atunci kmin > k. Pe baza acestei observatii putem dezvolta un algoritm ce cauta binar valoarea kmin ce are complexitatea O(log kmax (n + m)). O alta abordare se bazeaza pe o modificare usoara a

m).
Comisia a mai discutat posibilitatea de a propune problema folosind un graf neorientat. Atunci o solutie similara algoritmului Kruskal ar fi avut complexitate aproape de cea optima. Am fi putut folosi un radix sort pentru a sorta muchiile, iar apoi sa adaugam muchii in ordine crescatoare la graf pana cand nodul start si nodul destinatie ar fi fost in aceiasi componenta conexa. Pentru a gestiona componentele conexe am fi folosit structuri de multimi disjuncte. Aceasta solutie ar fi avut complexitatea O(kmax + m log*n).

 
 
Arbore
 

h2. Arbore

(problema medie clasele XI-XII)
O prima idee de rezolvare a problemei are o complexitate de O(1) la operatiile de tip update si O(n) la operatiile de tip query. Cand intalnim o operatie de tip 1 este necesar sa folosim un vector S[1..N] in care marcam aceste modificari. Astfel, adunand valoarea s la elementul S[p] vom observa ca suma pe care a primit-o un nod X este de fapt suma valorilor S[nod] unde nod reprezinta indicele nodurilor din drumul lui X pana la radacina arborelui. Deci, pentru o operatie de tipul 1 vom face o singura adunare, iar pentru o operatie de tipul 2 vom efectua o parcurgere in adancime pentru a cauta suma ceruta. Aceasta solutie obtine in jur de 30 de puncte.

Solutia care ar fi obtinut punctajul maxim se bazeaza pe reducerea problemei la nivel de vector, descrisa in paragraful precedent. Fie SEC = sqrt(N). Putem imparti vectorul de lungime N in SEC secvente de lungime SEC. Vom mai folosi 3 vectori A[1..N] reprezentand sumele pe fiecare element ce au fost adunate la inceputul secventelor de lungime SEC, C[1..SEC] reprezinta sumele ce s-au adunat pe intregile secvente, iar P[1..SEC][1..1 000 000] este o matrice binara unde P[i][j] = 1 daca exista un element din secventa i astfel incat A[element] = j. Aceasta idee ne ajuta sa rezolvam problema intr-o complexitate de O(sqrt(n)) atat pentru query cat si pentru update. Pentru ca memoria folosita sa fie rezonabila implementarea matricii P se face pe biti.

 
 
 
 
Pedefe
 

h2. Pedefe

(problema grea clasele XI-XII)
Problema cere determinarea numarului de subsiruri comune crescatoare al sirurilor S1 si S2 , care-l contin pe S3 ca subsir. Pentru a rezolva vom folosi metoda programarii dinamice. Se va construi un tabel A cu semnificatia: