h1. preONI 2005 runda #2 - solutii
(Creat de ==user(user="silviug" type="tiny")== la data de _2005-02-25_ categoria _Competitii_, autor(i) _Echipa devNet_)
==Include(page="template/raw")==
(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":http://www.infoarena.ro/Forum.
In continuarea acestui articol vom descrie solutiile oficiale ale problemelor. Daca aveti nelamuriri puteti sa puneti intrebari pe "forum":http://infoarena.ro/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! ;)
h3. Pascal
Ca sa calculam puterea la care apare factorul prim $p$ in descompunerea lui $n!$ se poate folosi urmatoare formula $f = [n/p] + [n/p^2^] + [n/p^3^] +$ ... ({$[]$} 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 ! / ((r-c) ! * 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.
Ca sa calculam puterea la care apare factorul prim $p$ in descompunerea lui $n!$ se poate folosi urmatoare formula $f = [n/p] + [n/p^2^] + [n/p^3^] +$ ... ({$[]$} 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! / ((r-c)! * 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 {$A{~c~}$} = puterea la care apare $p$ in decompunrea lui ({$r,c$}). $A{~c+1~}$ = {$A{~c~}$} + 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 ! / ((r-c)! * c !)$
O alta modalitate sa calculam puterea la care apare un factor prim $p$ in descompunerea lui este: fie {$A{~c~}$} = puterea la care apare $p$ in decompunerea lui ({$r,c$}). $A{~c+1~}$ = {$A{~c~}$} + 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! / ((r-c)! * c!)$
Aceasta a fost cea mai simpla problema de la clasele {$9-10$}, oricare din cele doua idei prezentate mai sus aducand punctaj maxim.
h4. 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:
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, Ai)) = Cnt(i - 1, j) + Cnt(i - 1, cmmdc(j, Ai))
== code(cpp) |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 10^9 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.
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 $10^9^$ 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{@]@}$} (ultimele 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.
h4. 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) = 2^card(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)... -
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) = 2^card(D(x))^-1$}. Multimile pentru principiul includerii si excluderii sunt chiar {$D(p)$}, unde $p$ este un numar prim. Intersectia {$D(p{~1~})$}, {$D(p{~2~})$}, {$D(p{~3~})$}.. este {$D(p{~1~} * p{~2~} * p{~3~}...)$}, oarecum evident, pentru $p$ distincte. Rezultatul este de forma:
Z(2 * 3 * 5) ...
== code(cpp) |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 2^x in O(N * L), altfel ca sa calculam Z(x) pentru fiecare ar fi nevoie de O(L * X) timp.
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 {$p{~1~}*p{~2~}*p{~3~}$}... 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 $2^x^$ in {$O(N * L)$}, altfel ca sa calculam $Z(x)$ pentru fiecare ar fi nevoie de $O(L * X)$ timp.
Cerere
h3. 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).
Problema este de dificultate medie. O rezolvare $O(N*lg(N))$ este usor de gasit, fiind asemanatoare cu una deja exista in arhiva, "Stramosi":http://infoarena.ro/problema/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
h3. 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) + h^2) 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 Theta(lg(N)), deci rezolvarea O(N*lg(N) + h^2) 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 [1]http://cgm.cs.mcgill.ca/~orm/rotcal.html. 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.
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) + h^2^)$ 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) + h^2^)$ 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":http://cgm.cs.mcgill.ca/~orm/rotcal.html. Idei de acolo v-ar fi ajutat sa rezolvati problema propusa recent la ".campion":http://campion.edu.ro/index.php, 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
h2. Incheiere
Pana la urmatorul concurs, BAFTA LA OJI!
References
Visible links
1. http://cgm.cs.mcgill.ca/~orm/rotcal.html
