Solutii preONI 2006, Runda finala

(Categoria Competitii, autor(i) Echipa Infoarena)

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.

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

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

(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²) 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 adauga 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

(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₁, 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 *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₁ 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² * log N) pe cazul defavorabil folosind cautari binare pentru gasirea punctelor, sau O(N²) pe cazul mediu folosind un hash (tabel de dispersie).

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: p₁, p₂, q₁, q₂, 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:

• (p₁, q₁, p₂, q₂) => (p₁+1, q₁-1, p₂, q₂), daca A[p₁ + 1] = A[q₁ - 1]
• (p₁, q₁, p₂, q₂) => (p₁+1, q₁, p₂, q₂-1), daca A[p₁ + 1] = B[q₂ - 1]
• (p₁, q₁, p₂, q₂) => (p₁, q₁-1, p₂+1, q₂), daca B[p₂ + 1] = A[q₁ - 1]
• (p₁, q₁, p₂, q₂) => (p₁, q₁, p₂+1, q₂-1), daca B[p₂ + 1] = B[q₂ - 1]

Aceasta ne duce la un algoritm de complexitate O(|A|² * |B|²), 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₁ + p₂ = |A| - q₁ + 1 + |B| - q₂ + 1), duce la un algoritm de complexitate O(|A|² * |B|) ce ar fi obtinut punctaj maxim.

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:

1. Cate mutari efectuam daca pornim din pozitia (X Y) si ajungem tot in (X Y) - lungimea ciclului care cuprinde pozitia (X Y). Daca pozitia (X Y) nu se afla pe un ciclu atunci lucrurile se simplifica (acesta este un caz special care se trateaza separat).
2. Cate mutari efectueaza fiecare robot pana ajunge in (X Y). Desigur, pot exista si roboti care nu ajung niciodata in (X Y).

Aflarea lungimii ciclului (punctul 1.) se face usor, pornind din pozitia (X Y), efectuand mutari pana se ajunge din nou in pozitia (X Y). Daca numarul de mutari depaseste modX*modY si nu am atins inca pozitia (X, Y), atunci aceasta nu se afla pe un ciclu. Complexitatea acestui pas va fi O(modX * modY).
Pentru a afla, pentru fiecare robot, numarul de mutari pentru a ajunge in (X Y), putem asocia un graf caroiajului, fiecarei celule din cele N*N corespunzandu-i un nod in graful orientat construit. Pentru fiecare celula (i j) vom adauga o muchie orientata in acest graf intre nodul corespunzator celulei (i j) si nodul corespunzator celulei ( [i*i + offsetX] modulo modX , [j*j + offsetY] modulo modY). Fiecare nod din acest graf va avea gradul de iesire 1, in consecinta, vor fi atatea muchii cate noduri sunt (adica N*N).
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

(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 algoritmului Dijkstra de drum minim, in care in loc sa pastram drumuri minime, pastram drumuri pt care muchia maxima are valoare cat mai mica. O implementare cu heapuri a acestui algoritm are complexitate O(m log n). De asemenea algoritmul Bellman Ford poate fi modificat usor pentru a ne rezolva problema, chiar daca acest algoritm are complexitatea O(n*m) in practica implementarea lui ce foloseste o lista se comporta cu mult mai bine. Ultimele trei rezolvari ar fi luat in jur de 70 de puncte.

Solutia oficiala se bazeaza tot pe o varianta a algoritmului Dijkstra, dar care in loc sa foloseasca un heap pentru a determina nodul i inca neexpandat cu drumul de la sursa la el de cost minim, foloseste niste liste. Aceasta abordare este identica cu cea din problema Car, si comisia se astepta ca multi concurenti sa rezolve perfect problema, asteptare infirmata de rezultatele din concurs. Cum ponderile muchiilor sunt numere de la 1 pana la 1000 inseamna ca in d[i] oricare ar fi nodul i va fi intotdeauna mai mica sau egala cu 1000. Vom folosi astfel 1000 de liste dublu inlantuite. In lista i vom tine minte nodurile x pentru care d[x] = i. Cand d[x] se micsoreaza inseram pe x intr-o lista mai mica, dar pentru a il sterge din lista veche vom folosi "lazy deletion". Adica atunci cand ajungem la lista i si vrem sa expandam nodul x verificam mai intai daca d[x] = i, daca nu inseamna ca d[x] < i si nodul x a fost expandat mai devreme, deci putem sa il ignoram. Acest algoritm are complexitate O(kmax + n + 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

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

O alta abordare ar fi reducerea problemei la nivel de vector. Am putea renumerota nodurile arborelui astfel incat subarborele fiecarui nod sa aiba id-uri consecutive. Acest lucru se poate face cu o parcurgere in adancime. Acum trebuie sa efectuam adunari pe intervale compacte de pe un vector, si trebuie sa gasim un element din vector ce are o anumita suma. Acest lucru se poate face, de asemenea in O(1) pentru update si O(N) pentru query usor. Aceasta solutie este mai rapida decat prima, deoarece nu foloseste apeluri recursive ale functiilor si efectueaza un numar mic de operatii. Asa s-ar fi luat 50-60 de puncte In cazul in care problema s-ar fi redus la nivel de vector dar atat update-ul cat si querry-ul s-ar fi efectuat in O(n) s-ar fi obtinut 30-40 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

(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:
A[k,i,j] = cate subsiruri comune crescatoare exista tinand cont doar de primele i valori ale lui S1, primele j valori ale lui S2, si care sa contina ca subsir primele k caractere din S3, iar ultima valoare din aceste subsiruri sa fie S1[i]. Valorile din tablou se vor calcula doar atunci cand S1[i] = S2[j], in rest valorile vor fi 0. In implementare, se vor pastra doar ultimele doua linii din tabloul A, A[k-1] si A[k].

In continuare se vor prezenta mai multe implementari bazate pe aceasta idee cu diferite complexitati si care aduc punctaje diferite.

Solutia O(N²*M²*P) - 30 puncte

Pentru a calcula A[k, i, j] ne vom uita fie in A[k-1] daca S1[i] = S2[j] = S3[k], fie in A[k] (S1[i] = S2[j], S1[i] != S3[k]). Se vor aduna valorile A[k (sau k-1), p, q] cu p<i, q<j si S1[p] ≤ S1[i].

Solutia O(N*M²*P) - 50 puncte

Se porneste de la solutia anterioara si se observa faptul ca pentru fiecare q care se considera se poate preprocesa suma A[k (sau k-1), p, q] pentru p < i intr-un tablou S. Dupa ce se calculeaza A[k, i, j] considerand doar acele q pentru care S2[q] ≤ S2[j], se actualizeza S[k, j].

Solutia O(N*M*P*Sigma) - 75 puncte

In cazul cel mai devaforabil numarul de valori distincte din siruri este min(N, M), dar se garanteaza in enunt ca Sigma (numarul de valori distincte) este ≤ 20 pentru inca 25% din teste. Pornind de la solutia anterioara, se observa ca , parcurgand j-ul de la 1 la M, nu este necesar sa consideram de fiecare data toate valorile q < j, aceste informatii putand fi actualizate in O(1). Deoarece trebuie sa numaram doar valorile cu S2[q] ≤ S2[j], se pastreaza intr-un vector V[x] , suma q-urilor < j , cu S2[q] ≤ x. Calculul lui A[k,i,j] se face in O(Sigma), iar dupa aceasta se actualizeaza vectorul V in O(1).

Solutia O(N*M*P*lgSigma) - 100 puncte

Solutia de 100 este asemantoare cu solutia de 75 de puncte, singura diferenta fiind folosirea unui arbore indexat binar pentru a face in O(lg Sigma) operatiile descrise mai sus.