Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2007-03-28 21:01:47.
Revizia anterioară   Revizia următoare  

preONI 2005 runda #2 - solutii

(Categoria Competitii, autor(i) Echipa devNet)

Desi s-a desfasurat intr-o zi de miercuri, runda a doua a concursului preONI a avut un numar aproape dublu de accesari fata de runda 1. Acest lucru se datoreaza probabil atat faptului ca olimpiada judeteana "bate la usa" cat si prezentei premiilor oferite de sponsorul nostru, Microsoft Romania.

In continuarea acestui articol vom descrie solutiile oficiale ale problemelor. Daca aveti nelamuriri puteti sa puneti intrebari pe forum.

Scopul principal al concursului preONI 2005 este antrenamentul pentru ONI. Nivelul problemelor a fost corespunzator, asa ca nu fiti descurajati la OJI daca n-ati facut foarte bine acum! ;)

Punctajele sunt multumitoare, fiindca de data asta nu s-au mai acordat cel putin 50p pentru solutii "brute force". Raportul de dificultate al problemelor a fost pastrat ca la runda 1.

In continuare vom prezenta solutiile oficiale ale autorilor problemelor.

Clasele 9-10

Clasament

PozitieNumeScor
1
cimiCristina Stancu-Mara
cimi
230
2
filipbFilip Cristian Buruiana
filipb
210
3
sefu_de_station iliescu
sefu_de_stat
200
3
arhirelBalaurul Arhirel
arhirel
200
3
macarieMacarie & Petronela
macarie
200
3
cyronsorin fagateanu
cyron
200
7
cristyRus Cristian
cristy
180
8
cyron16sorin fagateanu
cyron16
170

Sub pseudonimele arhirelBalaurul Arhirel arhirel si macarieMacarie & Petronela macarie se "ascunde", ca si la prima runda, echipa care va reprezenta Romania la finala ACM, formata din Mugurel Andreica, Marius Andrei si Ghinea Dan. Ei au concurat pe un singur calculator pentu a simula un concurs ACM. Stati linistit, premiile se dau doar concurentilor din ciclul de invatamant pre-universitar! De asemenea, se pare ca unii concurenti simt nevoia sa-si creeze mai multe conturi, Sorin Fagateanu avand 3 conturi in top 5 (cele 2 pe numele lui si contul cu numele "Ion Iliescu")... Tineti minte ca la un concurs "standard" nu aveti voie cu mai multe surse!

Pascal

Ca sa calculam puterea la care apare factorul prim p in descompunerea lui n! se poate folosi urmatoare formula f = [n/p] + [n/p2] + [n/p3] + ... ([] reprezinta partea intrega). Avand acesta formula putem traversa un anumit rand din triunghiul lui Pascal si pt fiecare element (r,c) putem calcula puterea la care apare d in descompunerea lui r
Imaginile trebuie neaparat sa fie atasamente ale unei pagini.
* c!)
. Atunci cand d nu este prim trebuie sa avem grija sa verificam daca respectivul element (r,c) are in descompunerea sa toti factori primi a lui d. Daca d=6 , elementul din (r,c) trebuie sa contina 2 si 3 in descompunerea sa, iar daca d = 4, trebuie sa contina 2 de cel putin doua ori. O alta modalitate sa calculam puterea la care apare un factor prim p in descompunerea lui este: fie Ac = puterea la care apare p in decompunrea lui (r,c). Ac+1 = Ac + puterea lui p in (r-c) - puterea lui p in (c+1). Acesta relatie se poate deduce din modul din care putem calcula elementul (r,c+1) din (r,c) folosind formula (r,c) = r
Imaginile trebuie neaparat sa fie atasamente ale unei pagini.
* c !)

Aceasta a fost cea mai simpla problema de la clasele 9-10, oricare din cele doua idei prezentate mai sus aducand punctaj maxim.

Secv

Subsirul trebuie sa contina toate elementele din sirul original in ordine crescatoare asa ca primul pas este sa ne formam acest subsir C. Avand acest subsir, parcurgem vectorul initial pentru a gasi pozitia de start a noii subsecvente. Dupa ce am gasit o posibila pozitie de start s incercam sa gasim subsirul C avand ca pozitie de start s. Din toate aceste subsecvente o alegem pe aceea cu lungimea minima. Asftel, complexitatea algoritmului ajunge la O(N*M), unde N este lungimea secventei initiale si M lungimea subsirului C. Problema se poate rezolva in aceeasi complexitate si cu programare dinamica, lasam acesta rezolvare ca exercitiu pentru concurenti!

Car

La prima vedere problema pare simpla si abordabila cu o cautare in latime, dar la o citire mai atenta problema se dovedeste putin mai grea. Cerinta e una de gasire a drumului minim intr-un graf in care nodurile sunt reprezentate de trei intregi (i,j,dir), i si j avand semnificatia liniei si coloanei din matrice iar dir reprezinta directia cu care am intrat pe pozitia curenta. Muchiile din graful nostru au costurile dupa cum s-a explicat in enunt. Pentru gasirea drumului putem folosi algoritmul Dijkstra care foloseste un heap pentru expandarea nodurilor, complexitatea unei astfel de rezolvari ar fi fost O(N*M lg (N*M)) dar un asemenea algoritm nu ar fi luat punctaj maxim. O observatie care ne poate reduce constanta algoritmului ar fi ca nu are rost sa folosim curbe de 180 sau de 135 de grade, pentru ca am fi ajuns in aceeiasi pozitie mai repede. Pentru a nu folosi memorie prea multa pentru reprezentarea nodurilor in coada noastra de prioritati am putea folosi un singur intreg in loc de trei astfel:

x = ((i - 1) * m + (j - 1)) * 8 + dir

si decodificarea ar fi

dir = x % 8; x /= 8;
j = (x % m) + 1;
i = (x / m) + 1;

Pentru a avea o viteza mai mare la codificare si decodificare putem folosi operatii pe biti: dir sa fie reprezentat pe 3 biti i, pe urmatorii 9 biti, iar j pe urmatorii 9 biti (i,j ≤ 500 < 29=512), astfel codificarea si decodificarea devin

x = (i << 9) + j + (dir << 18);
dir = x >> 18;
j = (x & 511);
i = (x >> 9) & 511;

Costurile muchiilor in graful nostru sunt mici si un algoritm ca cel
al lui Dijkstra nu tine cont de aceasta proprietate. Daca aceste costuri sunt mici atunci si costul final al drumului de la sursa la destinatie va fi mic deci ne permitem sa folosim pentru fiecare valoare posibila a costului unui drum de la sursa la destinatie cate o lista. Cand am determinat pentru un nod distanta minima de la sursa la el, il inseram intr-o astfel de lista, observam ca expandarea unui astfel de nod poate afecta numai urmatoarele 4 liste (prin expandare ne referim la actualizarea distantei minime de la sursa a vecinilor nodului curent). O astfel de rezolvare ar arata cam asa (pseudo-C):

for (dir =0; dir < 8; dir++)
    lst[0].add(starti,startj,dir,0);
current_cost = 0;
while (lst[0].size()+lst[1].size()+lst[2].size>0){
    while (lst[curent_cost % 3].size()>0) {
        x = lst[curent_cost % 3].pop();
        expand(x);
    }
    curent_cost++;
}

Am folosit numai trei liste pentru ca am tinut cont de optimizarea precizata mai sus de a nu folosi numai curbele la 0 grade, 45 grade si 90 grade. Fiecare nod poate fi expandat o singura data, si poate fi introdus in liste de cel mult trei ori, deci o astfel de solutie are complexitatea ca timp si ca spatiu O(N*M). Mergand mai departe pe aceasta idee putem obtine o rezolvare putin mai buna care injumatateste timpul de executie. Costurile au fost alese intr-un mod particular permitand ca o curba de 90 de grade sa aiba acelasi cost cu doua curbe de 45, una de 135 acelasi cost ca trei de 45 si una de 180 acelasi cost ca si patru de 45. Astfel putem modifica rezolvarea noastra si sa facem numai miscarile urmatoare: rotiri de 45 de grade pe loc si miscari in fata pe directia de mers. Astfel procedura de expandare actualizeaza numai trei noduri si in cursul procedurii de actualizare putem sa lucram numai cu lista curenta si cu lista urmatoare, pentru ca efectuam numai miscari de cost zero si unu. Aceasta observatie a micsorat numarul de liste si a micsorat numarul de calcule din metoda expand, cea mai frecvent utilizata in algoritm. O astfel de rezolvare ar fi adus punctajul maxim pe aceasta problema. Mentionam ca toate observatiile facute nu ar fi fost neaparat necesare pentru obtinerea unui punctaj maxim. Testele au fost facute in vederea obtinerii a 50 de puncte folosind cautare in latime simpla, 60-70 de puncte folosind Dijkstra cu heapuri si 90-100 de puncte folosind penultima rezolvare.

Clasele 11-12

Clasament

PozitieNumeScor
1
cimiCristina Stancu-Mara
cimi
230
2
filipbFilip Cristian Buruiana
filipb
210
3
sefu_de_station iliescu
sefu_de_stat
200
3
arhirelBalaurul Arhirel
arhirel
200
3
macarieMacarie & Petronela
macarie
200
3
cyronsorin fagateanu
cyron
200
7
cristyRus Cristian
cristy
180

Clasamentul la 11-12 este dominat de echipa ACM care a reusit sa rezolve toate cele 3 probleme (pe unul din cele doua conturi). Este de remarcat faptul ca primii 5 clasati au punctaje peste 200 de puncte.

Indep

Problema se poate rezolva in mai multe moduri. Limitele au fost alese astfel incat problema sa fie cat mai usoara. Vom prezenta cele doua solutii pe care le puteti gasi interesante:

Solutia 1

Prima solutie, si cea mai simpla, utilizeaza principiul programarii dinamice. Se calculeaza numarul de subsiruri din primele i elemente care sunt divizibile cu un numar j intre 1 si 1000. Sa notam acest numar cu Cnt[i][j]. Se obtine urmatoare recurenta pentru calculul acestor valori:

Cnt[i][cmmdc(j, A[i])] = Cnt[i - 1][j] + Cnt[i - 1][cmmdc(j, A[i])]

Odata calculate aceste valori solutia o vom avea in Cnt[N][1]. Numerele depasesc orice tip de date predefinit si trebuie utilizate numere mari. Limitele fiind destul de mari, folosirea bazei 10 este periculoasa, pe unele teste fiind necesar folosirea bazei 109 pentru a reduce timpul de executie. De asemenea si memoria se poate reduce, observand faptul ca pentru a calcula Cnt[i][j] ne sunt necesare doar valorile pentru Cnt[i-1][k] (ultima doua linii). Complexitatea acestei solutiei va fi O(N * K * L) unde K reprezinta valoarea maxima din sir si L lungimea maxima a numerelor mari.

Solutia 2

Cea de-a doua solutie, cu mult mai interesanta decat prima, foloseste principiul includerii se excluderii. Fie D(x) multimea numerelor din sir care sunt divizibile cu un anumit numar x, atunci numarul de submultimi formate doar din astfel de numere este Z(x) = 2card(D(x))-1. Multimile pentru principiul includerii si excluderii sunt chiar D(p), unde p este un numar prim. Intersectia D(p1), D(p2), D(p3).. este D(p1 * p2 * p3...), oarecum evident, pentru p distincte. Rezultatul este de forma:

Rezultat = Z(1) - Z(2) - Z(3) - Z(5)... +
           Z(2 * 3) + Z(2 * 5) + Z(3 * 5)... -
           Z(2 * 3 * 5) ...

Acesta se deduce din principiul includerii si al excluderii. Pentru a-l calcula efectiv, luam toate numerele x < 1000, produs de numere prime distincte, si vom adauga sau scadea Z(x) in functie de paritatea numarului de factori ai acestuia. Nu ne intereseaza decat produsele de numere prime distincte, care pot fi obtinute ca un produs p1*p2*p3... Complexitatea finala este sub O(N*K + N*L), unde K si L au semnificatia de mai sus. Folosim O(N*K) pentru a calcula D(x) pentru fiecare x, dar pentru fiecare x adunam sau scadem Z(x) o singura data, asa ca facem doar N operatii pe numere mari, o imbunatatire majora asupra primei rezolvari. Pentru a obtine aceasta complexitate este nevoie sa precalculam valorile lui 2x in O(N * L), altfel ca sa calculam Z(x) pentru fiecare ar fi nevoie de O(L * X) timp.

Cerere

Problema este de dificultate medie. O rezolvare O(N*lg(N)) este usor de gasit, fiind asemanatoare cu una deja exista in arhiva, Stramosi. Dar o astfel de rezolvare n-ar fi adus punctaj maxim in mod normal. Problema se poate rezolva printr-o simpla parcurgere in adancime din radacina implementand manual stiva DF-ului. Cand vom pune un nod n pe pozitia p in stiva, al K-lea stramos va fi nodul de pe pozitia p-K din stiva, pentru care s-a procesat deja valoarea ceruta. Complexitatea finala a algoritmului va fi O(N).

Rubarba

Aceasta problema e clasica in geometria computationala. O prima observatie care ne ajuta in rezolvare este ca numai punctele de pe infasuratoarea convexa influenteaza forma dreptunghiului minim. Deci primul pas in rezolvarea problemei este sa gasim infasuratoarea convexa a punctelor in O(N*lg(N)). Daca avem fixata o directie atunci e usor sa determinam in O(h) (unde h e numarul de puncte de pe infasuratoarea convexa) cele patru puncte ce marginesc dreptunghiul dupa directia aleasa si dupa directia perpendiculara. Folosind cautare binara pentru a determina cele patru puncte extreme, reducem astfel complexitatea la O(lg(h)). Observatia finala este ca un dreptunghi de arie minima ce contine o multime de puncte in interior trebuie sa aiba o latura paralela cu una din laturile infasuratorii convexe, aceasta idee este intuitiva dar demonstratia ei nu este foarte simpla. Complexitatea algoritmului ce rezolva problema poate fi O(N*lg(N) + h2) sau O(n*lg(n) + h*lg(h)) daca folosim cautarea binara. Testele folosite au fost generate aleator, generand aleator puncte in plan infasuratoarea convexa va avea cardinalul h teoretic egal cu Θ(lg(N)), deci rezolvarea O(N*lg(N) + h2) ar fi luat fara probleme punctaj maxim. Mentionam ca exista o tehnica numita "Rotating Calipers" care rezolva aceasta problema si altele similare in O(N*lg(N) + h), daca vreti sa cititi despre aceasta tehnica accesati pagina. Idei de acolo v-ar fi ajutat sa rezolvati problema propusa recent la .campion, care cerea separarea a doua poligoane convexe cu o dreapta, si o prolema propusa anul trecut la Bursele Agora care cerea determinarea distantei maxime ce exista intre oricare doua puncte dintr-o multime, si tot pe acea pagina gasiti demonstratia matematica a faptului ca dreptunghiul de arie minima ce contine in interior o multime de puncte are o latura paralela cu o latura a infasuratorii convexe.

Incheiere

Pana la urmatorul concurs, BAFTA LA OJI!