Solutii preONI 2006, Runda a 4-a

(Categoria Competitii, autor(i) Echipa info-arena)

Suntem bucurosi sa va anuntam ca Runda a 4-a concursului preONI 2006 s-a incheiat. In acest articol va vom prezenta solutiile oficiale ale celor 7 probleme propuse precum si cateva aprecieri dupa cele patru probe de foc.

S-a consumat si al patrulea act al bataliei si odata cu el si etapa on-line a concursului preONI. S-a tras linia si s-au desemnat fericitii calificati in runda finala (atentie! verificarea inca nu a fost facuta, dar cu asta ne vom ocupa in urmatoarea perioada).

Aruncandu-ne ochii pe clasamentele Rundei 4, constatam ca participantii au tras tare pe ultima suta de metri vrand sa ne contrazica previziunile sumbre dupa Runda 3. Desi nivelul de dificultate al problemelor a fost un pic mai scazut fata de runda precedenta, concurentii s-au dovedit mult mai conectati la concurs - suspectam ca apropierea olimpiadelor ar fi cauza. Asadar am avut punctaje aproape maxime (275, 255) obtinute in viteza maxima de primii doi clasati la clasa a 9-a - Bogdan Tataroiu si Sima Mihai Cotizo, un punctaj maxim la clasa a 12-a realizat de Costea Andrei care a reusit, dupa un start mai putin reusit in rundele precedente, sa treaca la pas pe langa ceilalti info-atleti, unii dintre ei deja nume mari. De data aceasta, concurentii de la clasa a 10-a nu s-au lasat mai prejos fata de celelalte grupe de varsta si, avand un set clar mai usor decat precedentul, au adunat in ritm de maraton punctaje frumoase care au atins si depasit limita (legal admisa) de 200. Felicitari pentru aceasta realizare lui Vlad Dumitriu si Bogdan Stoica. In concluzie, am asistat la un concurs bine organizat (felicitari comisiei!) si la un sprint de sanatate din partea concurentilor (felicitari mai ales lor!) care ne-au convins inca o data ca tinerii nostri sunt pregatiti sa fuga mancand pamantul pentru gloria si renumele olimpiadelor nationale si internationale.

Una peste alta, s-a incheiat o etapa frumoasa a concursului in care am pus mult suflet. Normal, pot fi doar 30 de participanti fericiti de rezultate. Ii felicitam pe cei calificati si abia asteptam sa-i vedem in finala. Ii felicitam si pe ceilalti care nu au putut sa-si tina suflul pana in final, pierzand locurile calificabile. Noi le uram cat mai multe succese, sa mai alerge vreo cateva sute de probleme (incepand cu cele din Arhiva noastra) si sa ne intalnim cu ei mult mai pregatiti la startul urmatorului preONI.

In urmatoarele pagini vom incerca sa explicam solutiile problemelor. Asa cum v-ati obisnuit, va puteti lamuri orice vi se pare neclar sau vag explicat intreband pe forum, unde vom incerca sa raspundem cat mai promt. Va asteptam cu intrebari si sugestii (asigurati-va ca pareririle va sunt auzite!)

NextSeq
(problema simpla clasa a 9-a)

Este usor de observat ca cele doua siruri pot fi interpretate ca numere in baza N (numarul de elemente din setul X). Acest lucru se poate efectua sortand numerele din setul X si asociind fiecaruia o valoare intre 0 si N-1 (procedeul poarta numele de normalizare). Stiind acest lucru, doua solutii sunt posibile.

Cea mai usoara dintre ele este sa calculam sirul ce il urmeaza pe A (numarand in baza N) pana cand obtinem sirul B. Deoarece se garanta faptul ca sunt mai putin de 100 de siruri intre A si B, acest pas se va executa de maxim 100 de ori. Ne punem problema calcularii sirului care urmeaza dupa sirul A. Putem afla sirul care-l urmeaza pe A in complexitate O(M) - M este lungimea sirului A - simuland operatia de adunare cu 1 in urmatorul mod: parcurgem sirul A incepand cu ultimul element pana cand gasim un element mai mic decat N-1 (interpretandu-l in baza N); incrementam acel numar si numerele egale cu N-1 intalnite pana la la el, le egalam cu 0 (cea mai mica valoare). Singurul caz interesant este acela cand A are toate elementele egale cu valoarea maxima dar este usor de tratat. Complexitatea finala va fi O(D*P) - P este lungimea sirului B iar D este numarul de siruri aflate intre A si B.

Solutia mai rapida, dar ceva mai dificil de implementat, se baza pe operatia de scadere pe numere mari. Astfel, dupa ce am calculat reprezentarile sirurilor A si B in baza N, putem efectua o scadere pe numere mari pentru a afla numarul de siruri cuprinse intre A si B. Complexitatea solutiei este O(P) - P este lungimea sirului B.

Ambele solutii obtin punctaj maxim, prima fiind ceva mai usoara, putandu-se ajunge la ea si prin abordari care nu tin cont de reprezentarea sirurilor in baza N.

GFact
(problema medie clasa a 9-a)

Primul pas in rezolvarea problemei il reprezinta factorizarea numarului P. Acest lucru se poate realiza intr-o complexitate O(√P). Odata obtinuta factorizarea, vom avea o relatie de forma:
P = T₁^R1 * ... * T_K^RK
Imediat rezulta:
A = T₁^{R1 * Q} * ... * T_K^{RK * Q}
Al doilea pas este sa observam ca daca aflam pentru fiecare T_i, B_i astfel incat B_i! se divide la T_i^{Ri * Q} atunci B (numarul cautat in problema) este maximul dintre B_i. Implicatia imediata e ca putem sa ne ocupam de fiecare numar prim in parte fara sa tinem cont de celelalte.

Al treilea pas consta in determinarea B_i-urilor cu ajutorul cautarii binare. Pentru o valoare candidata X (din cautarea binara) trebuie sa calculam puterea lui T_i in descompunerea lui X!. Acest lucru se afla simplu ca fiind [X/T_i] + [X/T_i²] + ... (unde prin [x] intelegem partea intreaga a lui x). Cautarea binara se poate optimiza observand ca B_i este intotdeauna divizibil cu T_i, ba mai mult nu va fi mai mare decat (R_i * Q) * T_i (observatie necesara obtinerii punctajului maxim). In concluzie, vom cauta binar o valoare intreaga K in intervalul [1, R_i * Q] astfel incat B_i = K * T_i sa aiba propietata ca B_i! se divide la T_i^{Ri * Q}. Va puteti intreba de ce putem cauta binar. Este simplu: daca o valoare X are propietatea ca X! se divide la Y (unde lui X si Y le putem da semnificatiile dorite de noi) atunci, evident, si (X + 1)! se divide la Y.

Solutia finala va avea complexitatea O(√P * log Q * log Q). Exista o serie de solutii intermediare care permiteau obtinerea de punctaje suficient de mari si de aceea problema a fost considerata medie desi rezolvarea completa este destul de dificila.

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

Primul pas al algoritmului este calcularea numarului de aparitii ale fiecarei litere in matricea de N*N. Prima idee care ne vine in minte este ca pentru toate submatricile posibile sa calculam numarul de aparitii ale fiecarei litere si sa comparam cu valorile care trebuie obtinute. Acest algoritm are complexitatea O(M^2*(N+S)), unde S este dimensiunea alfabetului. Aceasta abordare obtine 50 de puncte.
Vom verifica pentru toate cele (M-N)² matrici posibile daca sunt sau nu permutari ale matricii-template. Apoi, pentru fiecare litera a alfabetului, efectuam urmatoarea preprocesare pentru a putea calcula in O(1) numarul de aparitii ale literei din orice submatrice: T_i,j = numarul de aparitii pe pozitii (x, y) cu 1 ≤ x ≤ i si 1 ≤ y ≤ j.

Relatia de recurenta este T_i,j = T_i-1,j+T_i,j-1-T_i-1,j-1, la care se adauga 1 daca si numai daca pe pozitia (i, j) se afla litera pe care o cautam. In aceste conditii, numarul de aparitii ale literei curente in submatricea cu colturile in (i-N+1, j-N+1) si (i, j) este T_i,j-T_i-N,j-T_i,j-N+T_i-N,j-N. Aceasta solutie are complexitatea O(M^2*S). Daca se foloseste O(M^2*S) memorie se obtin 70-80 de puncte, iar pentru punctaj maxim este necesara reducerea la O(M²). Acest lucru poate fi realizat folosind doua matrici, una in care tinem minte daca pentru o anumita pozitie s-a gasit vreo litera pentru care numarul de aparitii nu coincide cu cel dorit, si una in care se efectueaza preprocesarea pentru litera curenta. O alta optimizare, mult mai nesimnificativa, si care nu este necesara pentru 100 de puncte, este renuntarea la verificarea pentru ultima litera, deoarece daca primele 25 de litere s-au potrivit, iar numarul de litere este constant, e clar ca si cea de-a 26-a litera se va potrivi.

Lista lui Andrei
(problema usoara clasa a 10-a)

Problema se rezolva folosind programare dinamica. Putem tine o matrice V_1..N1..26 unde V_i,j reprezinta numarul de siruri de lungime i ce contin ultima litera j. Incepem completarea matricii in ordine crescatoare a lungimii sirurilor, iar V_i,j se obtine prin insumarea valorilor V_i-1,k, pentru orice k a.i perechea (k, j) sau (j, k) sa nu se regaseasca in lista. Acest rationament conduce la un algoritm in O(N * Σ²), unde Σ reprezinta marimea alfabetului (in cazul nostru 26).

Calcul
(problema grea clasa a 10-a, problema medie clasele 11-12)

Deoarece se cer doar ultimele C cifre se va lucra modulo 10^C. Asadar, la primul pas se va calcula A modulo 10^C, adica ne intereseaza doar ultimele C cifre din A.
O prima solutie pentru a calcula A¹ + A² + ... + A^B este de calcula Aⁱ in O(lg i) pentru fiecare i folosind algoritmul clasic de ridicare la o putere in numar logaritmic de pasi (Cormen, capitolul 33). Aceasta solutie ar fi adus doar 20p.

Suma prezentata este o progresie geometrica clasica, si se poate calcula folosind formula (A^B+1-A) / (A-1). Calculul lui A^(B+1) se face folosind acelasi algoritm mentionat mai sus in O(lg B) (lg = logaritm in baza 2). Pentru a efectua impartirea modulo 10^C, trebuie sa existe un invers multiplicativ pentru A-1 , modulo 10^C, lucru garantat doar pentru 50% din teste (cmmdc(A-1, 10^C) = 1). Inversul multiplicativ poate fi calculat folosind algoritmul Euclid extins sau teorema lui Fermat: X^phi(N) = 1 (mod N) pentru cmmdc(X, N) = 1 si phi(N) = indicatorul lui Euler, cate numere < N sunt prime cu N. Din teorema reiese ca X^phi(N)-1 = X^-1 (mod N), asadar inversul poate fi calculat algoritmul de ridicare la o putere mentionat mai sus ($phi(10^C)$ poate fi calculat usor). Un caz special la aceasta solutie apare atunci cand A = 1. Aceasta solutie n-ar fi adus decat 50p si necesita cunostiinte de matematica de clasa a 12-a.

Exista o solutie mult mai accesibila pentru clasele a 10-a si a 11-a, folosind
relatiile:
S(A,2*B) = S(A,B) * (1+A^B)
S(A,2*B+1) = A * (1+S(A,2*B))
Cum numarul B este dat in baza 16, parcurgerea bitilor acestuia se face usor, simuland algoritmul de mai sus. Daca A^B se calculeaza la fiecare pas, complexitatea va fi O(lg² B), obtinand 60p. O solutie O(lg B) de 100 de puncte se poate obtine calculand in paralel valorile S(A,B) si A^B. O ultima "problema" care ar fi putut exista este faptul ca se cer ultimele C cifre, nu rezultatul modulo 10^C; spre exemplu, daca C = 4 si rezultatul modulo 10⁴ ar fi fost "123", in fisierul de iesire trebuia afisat "0123".

Distante minime
(problema usoara clasele 11-12)

Problema se rezolva folosind algoritmul lui Dijkstra pornind din nodul 1. Astfel pe langa vectorul D_1..N in care tinem distantele minime vom mai folosi un vector P_1..N in care tinem pentru fiecare nod i numarul de drumuri de lungime D_i. Cand relaxam o muchie vom face update, daca este cazul, atat in vectorul D cat si in vectorul P.

Deoarece costul drumurilor a fost definit ca produs de muchii, in vectorul D putem ajunge sa avem numere cu mii de cifre. O implementare cu numere mari a algoritmului descris mai sus nu este destul de eficienta, ea obtinand aproximativ 75 de puncte. Pentru a obtine punctajul maxim este necesara logaritmarea costului fiecarei muchii intr-o baza oarecare. Astfel putem transforma produsul in suma, folosind o proprietate a logaritmilor, fapt ce duce la o implementare simpla si rapida, folosind doar date de tip double.

Popandai
(problema grea clasele 11-12)

Mai intai vom calcula, pentru fiecare pereche de puncte A si B din punctele ce reprezinta vizuinele, in sirul sub_AB cate puncte din restul de n se afla sub segmentul de dreapta determinat de A si B. Aceasta preprocesare poate fi efectuata in O(n² log n) cu un algoritm inteligent sau poate fi efectuata in O(n³) cu metoda naiva care verifica pentru fiecare punct daca este situat pe intervalul [A.x, B.x] si este sub dreapta determinata de cele doua puncte. Preprocesare vom putea pentru fiecare triunghi ABC sa aflam in timp O(1) cate puncte are in interior: presupunem fara a restrange generalitatea ca A.x ≤ B.x ≤ C.x, daca punctul B e deasupra dreptei AC atunci numarul de puncte din interiorul lui ABC este sub_AB + sub_BC - sub_AC, iar daca B este sub dreapta AC atunci numarul de puncte este sub_AC - sub_AB - sub_BC - 1.

Orice patrulater, fie el concav sau convex, are o diagonala interna. Daca fixam un segment PQ ca fiind diagonala interna putem sa incercam sa gasim pentru fiecare x triunghiul PQR de arie minima pentru care punctul R este deasupra dreptei PQ si care contine in interior cel putin x puncte, iar apoi sa gasim un triunghi PQS de arie minima cu varful S sub dreapta PQ ce contine in interior cel putin k-x puncte. Ariile minime ale acestor triunghiuri se pastreaza in doua siruri over si under iar aria minima a unui patrulater cu o diagonala PQ va fi min(over_x + under_k-x | unde x ia toate valorile de la 0 la k). Folosind artificiul explicat mai sus putem determina in O(1) numarul de puncte ce se afla in interiorul unui triunghi, si astfel sirurile over si under pot fi calculate in O(n). Complexitatea totala a algoritmului este O(n³) pentru ca avem O(n³) calcule in faza de preprocesare si pentru fiecare n(n-1)/2 diagonale vom efectua O(n) calcule.