Dupa cele patru runde online de concurs cu adevarat dure, cei 29 de concurenti si-au facut aparatia, de prin toate ungherele tarii, pe terenul de lupta. Desi in prima seara, la deschiderea ne-scortoasa si informala, concurentii isi zambeau sincer si fara vreun resentiment, in aer plutea "emotia, tracul, tensiunea, stress-ul".. Calmul dinaintea furtunii.. Venea marea confruntarea, batalia bataliilor, in urma careia trebuiau alesi castigatorii preONI 2006.
Concursul s-a dovedit a fi o adevarata proba de foc, o batalie cu fum de creiere din plin si cu multe iesiri la toaleta (vezi [1]Cronica). Problemele, la limita imposibilului. Comisia a nascocit cele mai nastrusnice provocari pentru o finala in care participau concurenti adevarati, gata sa dea peste cap toate topurile Olimpiadelor ce vor voni. Muschi incordati, "trac, tensiune, stress". La sfarsit, punctaje reflectand truda demna de admirat a unor campioni alergand pe ultima suta de metri a unei curse in 5 acte. Castigatorii au fost sa fie, de acesta data, Cosmin Gheorghe la clasa a IX a, Simion Alexandru la clasa a X a si Marin Radu la clasele XI-XII. Ii felicitam pe ei si, in aceeasi masura, pe toti participantii care, desi au ratat premiile, cu siguranta au castigat prieteni noi.
Concursul s-a dovedit a fi o adevarata proba de foc, o batalie cu fum de creiere din plin si cu multe iesiri la toaleta (vezi "Cronica":preoni-2006/finala/cronica). Problemele, la limita imposibilului. Comisia a nascocit cele mai nastrusnice provocari pentru o finala in care participau concurenti adevarati, gata sa dea peste cap toate topurile Olimpiadelor ce vor voni. Muschi incordati, "trac, tensiune, stress". La sfarsit, punctaje reflectand truda demna de admirat a unor campioni alergand pe ultima suta de metri a unei curse in 5 acte. Castigatorii au fost sa fie, de acesta data, Cosmin Gheorghe la clasa a IX a, Simion Alexandru la clasa a X a si Marin Radu la clasele XI-XII. Ii felicitam pe ei si, in aceeasi masura, pe toti participantii care, desi au ratat premiile, cu siguranta au castigat prieteni noi.
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.
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 "forum":http://forum.infoarena.ro/.
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
h3. (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]$.
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 abordare care insa nu conduce la punctaj maxim este programarea dinamica, calculand sol[i][j] cantitatea maxima de lana care se poate alege cu primele i oi pana la momentul j. Raspunsul se va gasi in sol[n][T_max]. Complexitatea este O(n^2) si ar obtine aproximativ 50-60 de puncte.
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.
h3. (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 abordare care insa nu conduce la punctaj maxim este programarea dinamica, calculand $sol{~i,j~}$ cantitatea maxima de lana care se poate alege cu primele $i$ oi pana la momentul {$j$}. Raspunsul se va gasi in {$sol{~n,T_max~}$}. Complexitatea este $O(n^2^)$ si ar obtine aproximativ $50-60$ de puncte.
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.
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.
Odata fixata rotatia pe care o consideram (inclusiv cea de 0 grade), presupunem pe rand pentru fiecare punct i > 1 ca P_1 se transforma in P_i, si verificam daca aceasta presupunere conduce la o solutie valida. Presupunerea facuta stabileste in mod unic care este translatia efectuata. Retinem un vector P[i] = punctul in care se transforma al i-lea punct dupa aplicarea rotatiei fixate si a translatiei determinate, sau -1 daca punctul transformat nu se regaseste printre cele initiale. Pentru a realiza in mod eficient aceasta operatie, la inceputul algoritmului punctele se sorteaza cu o functie de comparare oarecare si la fiecare pas punctul dorit se cauta binar in acest vector, in O(log N). Eventual s-ar putea folosi un tabel de dispersie, insa consideram ca aceasta structura de date este prea complicata pentru nivelul clasei a 9-a si nu era necesara pentru obtinerea punctajului maxim.
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).
h3. (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~}$}.
Odata fixata rotatia pe care o consideram (inclusiv cea de $0$ grade), presupunem pe rand pentru fiecare punct $i > 1$ ca $P{~1~}$ se transforma in {$P{~i~}$}, si verificam daca aceasta presupunere conduce la o solutie valida. Presupunerea facuta stabileste in mod unic care este translatia efectuata. Retinem un vector $P{~i~}$ = punctul in care se transforma al {$i$}-lea punct dupa aplicarea rotatiei fixate si a translatiei determinate, sau $-1$ daca punctul transformat nu se regaseste printre cele initiale. Pentru a realiza in mod eficient aceasta operatie, la inceputul algoritmului punctele se sorteaza cu o functie de comparare oarecare si la fiecare pas punctul dorit se cauta binar in acest vector, in {$O(log N)$}. Eventual s-ar putea folosi un tabel de dispersie, insa consideram ca aceasta structura de date este prea complicata pentru nivelul clasei a 9-a si nu era necesara pentru obtinerea punctajului maxim.
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).
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.
h3. (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: {$p{~1~}$}, {$p{~2~}$}, {$q{~1~}$}, {$q{~2~}$}, 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$}.
Se iau 4 cazuri de tranzitie intre stari:
(p1, q1, p2, q2) => (p1 + 1, q1 - 1, p2, q2), daca A[p1 + 1] = A[q1 - 1]
(p1, q1, p2, q2) => (p1 + 1, q1, p2, q2 - 1), daca A[p1 + 1] = B[q2 - 1]
(p1, q1, p2, q2) => (p1, q1 - 1, p2 + 1, q2), daca B[p2 + 1] = A[q1 - 1]
(p1, q1, p2, q2) => (p1, q1, p2 + 1, q2 - 1), daca B[p2 + 1] = B[q2 - 1]
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.
* ({$p{~1~}, q{~1~}, p{~2~}, q{~2~}$}) => ({$p{~1~}+1, q{~1~}-1, p{~2~}, q{~2~}$}), daca {$A[p{~1~} + 1] = A[q{~1~} - 1]$}
* ({$p{~1~}, q{~1~}, p{~2~}, q{~2~}$}) => ({$p{~1~}+1, q{~1~}, p{~2~}, q{~2~}-1$}), daca {$A[p{~1~} + 1] = B[q{~2~} - 1]$}
* ({$p{~1~}, q{~1~}, p{~2~}, q{~2~}$}) => ({$p{~1~}, q{~1~}-1, p{~2~}+1, q{~2~}$}), daca {$B[p{~2~} + 1] = A[q{~1~} - 1]$}
* ({$p{~1~}, q{~1~}, p{~2~}, q{~2~}$}) => ({$p{~1~}, q{~1~}, p{~2~}+1, q{~2~}-1$}), daca {$B[p{~2~} + 1] = B[q{~2~} - 1]$}
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 {$p{~1~} + p{~2~} = |A| - q{~1~} + 1 + |B| - q{~2~} + 1$}), duce la un algoritm de complexitate $O(|A|^2^ * |B|)$ ce ar fi obtinut punctaj maxim.
h2. Robotei
(problema grea clasa a X-a)
