Solutii preONI 2006 - Runda a 3-a
(Categoria Competitii, autor(i) Echipa infoarena)
Runda a 3-a concursului preONI 2006 s-a incheiat. Acest articol va prezinta solutiile oficiale ale celor 7 probleme propuse precum si cateva aprecieri pe marginea concursului.
S-a incheiat si cea de-a treia runda a concursului preONI 2006. Ca de obicei, la fiecare grupa au existat 3 probleme cu nivele diferite de dificultate: usor, mediu, greu. Spre deosebire de runda precedenta, problemele au fost ceva mai accesibile facand mai usoara obtinerea unui punctaj mediu pentru participantii de la toate cele trei grupe. Salutam primul punctaj maxim realizat de Cosmin Gheorghe, participant la clasa a IX-a. Desi nivelul de dificultate al problemelor este unul ridicat (comparativ cu cel de la nationale), nu putem sa nu remarcam faptul ca, la clasa a X-a, nivelul de pregatire al concurentilor este ceva mai scazut fata de celelalte grupe, in conditiile in care olimpiadele se apropie. Ii sfatuim pe toti participantii sa se pregateasca si mai consistent de acum incolo, utilizand si platforma pe care le-o pune la dispozitie InfoArena.
Inainte de ultima runda, la clasa a IX-a, avem deja doi concurenti care s-au detasat de pluton in persoana lui Gheorghe Cosmin si Tataroiu Bogdan, lupta fiind inca acerba pentru ultimele locuri calificabile. La clasa a X-a avem un clasament destul de echilibrat, cu elevii clasati primii fara prea mari emotii inainte de ultima runda, dar cu multe semne de intrebare pentru cei clasati pe locurile 8-10. La clasele XI-XII avem o batalie frumoasa, cu multe punctaje peste 300 si o situatia foarte confuza catre ultimele locuri calificabile.
Le uram tutoror succes si fie ca cei mai buni sa mearga in finala!
Numarare triunghiuri
(problema simpla, clasa a 9a)
Pentru a rezolva problema trebuie cunoscuta conditia de existenta a unui triunghi cand avem lungimile segmentelor. Fie a, b, c lungimile laturilor in ordine nedescrescatoare. Se poate forma un triunghi cu ele doar daca a + b ≥ c (este usor de intuit de ce).
Acum putem rezolva problema in O(N3) verificand toate triunghiurile posibile care s-ar putea forma si numarandu-le doar pe cele ce respecta conditia de mai sus. Aceasta solutie ar trebui sa ia in jur de 75 de puncte.
Pentru a rezolva mai eficient problema este necesar sa sortam nedescrescator vectorul cu lungimile segmentelor. Acum putem fixa segmentele a si b si putem cauta binar pozitia maxima din vector a segmentului c care respecta a + b ≥ c. Deci numarul de triunghiuri care se pot forma avand primele doua laturi a si b este egal cu numarul de elemente din vector de dupa b si pana la c (pentru fiecare triunghi luam segmentele a, b, c in ordine crescatoare dupa indicii din vector, evitand astfel numararea unui triunghi de doua ori). Deci complexitatea acestei solutii este O(N2 log N) si ar fi luat fara probleme punctajul maxim.
Putem imbunatati solutia de mai sus la o complexitate O(N2), eliminand cautarea binara. Aceasta solutie va lasam sa o descoperiti voi.
Divizori primi
(problema medie, clasa a 9a)
Fiind vorba de maxim 1.000.000 numere se poate calcula pentru fiecare in parte cati divizori primi are. Pentru acest lucru se foloseste ciurul lui Erathostene si se construieste vectorul ndpi - numarul de divizori primi ai lui i. Parcurgem numerele din 1 in 1 si in momentul in care am dat peste un numar care are 0 divizori primi pana in acest moment inseamna ca am gasit un nou numar prim si vom actualiza vectorul ndp pentru toti multiplii lui si implicit pentru el (numarul fiind propriul sau divizor). Apoi se construieste o matrice soli,j care retine care este cel mai mare numar mai mic sau egal cu i cu j divizori primi (adica exact raspunsurile pentru problema noastra). Pentru a construi linia i se copiaza linia i-1 si se actualizeaza soli,ndpi=i.
Pentru mai multe detalii despre cum functioneaza ciurul lui Erathostene puteti accesa articolul.
Subsir 2
(problema grea clasa a 9a, problema medie clasa a 10a, problema usoara clasele 11-12)
Problema poate fi considerata asemanatoare cu cea a celui mai lung subsir crescator, avand o rezolvare similara de complexitatea O(N2) folosind metoda programarii dinamice.
Se vor construi doi vectori:
- Ai = lungimea celui mai scurt subsir crescator maximal care incepe cu pozitia i
- Ti = urmatorul element dupa pozitia i in cel mai scurt subsir crescator maximal care incepe cu i (pentru reconstiutire)
Pentru fiecare i, se va cauta un j > i astfel incat Vi ≤ Vj (unde V este vectorul de numere) si se alege acela cu Aj minim, Ai devenind Aj+1, iar Ti devine j. Daca nu exista nici un j, Ai se initializeaza cu 1 si Ti cu i.
Ca sirul construit sa fie maximal trebuie ca atunci cand verificam j-urile pentru un i fixat, j-ul respectiv sa fie "dominant", in sensul ca sa nu existe un i < k < j astfel incat Vi ≤ Vk ≤ Vj, deoarece sirul construit cu primul element in i si al doilea in j ar putea fi extins inserand k intre i si j. Verificarea pentru acest k se poate face in O(N), obtinand o solutie O(N3) care ar fi adus 50-60p. Pentru a face verificarea in O(1), facem observatia ca ne intereseaza doar acel Vk minim care este ≥ Vi. Pe masura ce se avanseaza cu variabila j, se pastreaza o variabila min, reprezentand minimul dintre valorile Vj parcurse pana acum, care sunt ≥ Vi.
Astfel, cand se ajunge la un j, se verifica inainte daca Vj < min (conditie necesara pentru a construi un sir maximal). Un ultim detaliu in solutie este obtinerea solutiei minime din punct de vedere lexicografic. Cand se selecteaza j-ul pentru fiecare i, pe langa faptul ca se alege acela cu Aj minim, in caz de egalitate se va alege acela cu valoarea Vj minima. Selectarea este corecta deoarece nu vor exista j1, j2 cu Aj1 si Aj2 minim , iar Vj1 = Vj2.
Problema se poate rezolva mai bine intr-o complexitate O(N*lg2 N) folosind structuri de date avansate, astfel transformandu-se intr-o problema de clasele 11-12 grea, sau chiar o problema de finala. Lasam aceasta rezolvare ca exercitiu pentru cititor.
Sum
(problema usoara, clasa a 10a)
Vom face o prima observatie:
- (n, d) = 1 <=> (n, n - d) = 1, (n, n + d) = 1
Fie a = phi (n), indicatorul lui Euler. Fie b numarul de numere prime cu n cuprinse intre n si 2 * n.
Deoarece (n, d) = 1 <=> (n, n + d) = 1, a ≤ b. Deoarece (n, d) = 1 <=> (n, n - d) = 1, b ≤ a => b = a. Fie x1, x2, .. xa numerele < n si prime cu n => numerele cuprinse intre n si 2 * n si prime cu n vor fi x1 + n, x2 + n, .. xa + n.
Conform observatiei facute, (n, n - x1) = 1, (n, n - x2) = 1, .. (n, n - xa) = 1 =>
xa = n - x1 <=> x1 + xa = n
xa-1 = n - x2 <=> x2 + xa-1 = n
...
x1 = n - xa <=> xa + x1 = n
Fie S1 suma numerelor prime cu n si mai mici ca n, fie S2 suma numerelor prime cu n, cuprinse intre n si 2 * n.
Adunand cele a egalitati, obtinem 2 * S1 = a * n => S1 = (a * n) / 2.
S2 = a * n + S1 => S1 + S2 = 2 * a * n.
Se foloseste o singura data ciurul lui Erathostene pentru a determina functia phi pentru toate intrebarile. Se poate consulta articolul despre cirulul lui Erathostene.
Pavare 2
(problema grea, clasa a 10a)
Problema se rezolva cu programare dinamica. Utilizam urmatoare structura de date:
- V[i][j][0] = numarul de posibilitati pentru a pava i metri astfel incat primele j placi sa fie albe
- V[i][j][1] = numarul de posibilitati pentru a pava i metri astfel incat primele j placi sa fie negre
Relatiile de recurenta sunt acum usor de dedus. Odata calculata matricea putem raspunde foarte usor primei cerinte, facand suma V[N][i][0] (pentru 1 ≤ i ≤ A) si V[N][i][1] pentru (1 ≤ i ≤ B).
Pentru a 2-a cerinta incercam sa construim a K-a secventa lexicografica de la inceput catre sfarsit. Astfel, la fiecare pas incercam sa punem o segventa de tipul '0...01' care sa contina un numar maxim de '0'. Daca la pasul curent nu putem pune nici un '0' atunci vom pune o secventa de tipul '1..1' care sa contina un numar minim de 1. Numarul de '0'-uri sau de '1' pe care il punem il vom calcula cu ajutorul matricei precalculate la prima cerinta. Astfel, daca putem pune p de '0' inseamna ca numarul de posibilitati pentru a completa restul solutiei daca punem cel putin p de '0' la inceput este mai mare sau egal cu K. Alegem cel mai mare numar p cu proprietatea de mai sus. Daca p nu exista, incercam sa punem cat mai putini '1' in aceeasi maniera. Continuam apoi cu restul secventei, iar din K scadem numarul de solutii peste care am "sarit".
Count
(problema medie, clasele 11-12)
Inainte de a prezenta solutia, enumeram cateva propietati ale grafurilor planare care se vor dovedi utile mai departe:
- Orice graf planar contine un nod cu grad mai mic decat 6
- Numarul maxim de muchii pe care il poate avea un graf planar este 3 * N - 6, unde N este numarul de noduri. Asadar O(M)=O(N) (M fiind numarul de muchii).
- Grafurile planare nu contin clici (subgrafuri complete) cu mai mult de 4 noduri (nu se poate desena in plan o clica de 5 noduri fara a intersecta muchiile acesteia).
Consecinta imediata a propietatii numarul 3 este ca intr-un graf planar vom avea clici de maxim 4 noduri. Cum cazurile in care clica cu numar maxim de noduri este compusa dintr-unul sau doua noduri este banal, ne vom concentra atentia pe cazurile in care avem clici de 3 sau 4 noduri.
Stiind acest lucru, un algoritm O(N2) este usor de obtinut (si multi dintre concurenti au reusit acest lucru pentru ~70 de puncte). Ideea este urmatoarea:
- Cazul clicilor de 3 noduri: se numara toate clicile care includ o anumita muchie incercand sa construim un triunghi impreuna cu fiecare nod din graf. Asadar pentru fiecare muchie, incercam cu fiecare nod (mai putin cele doua capete ale muchiei) sa construim o clica de 3 noduri. Complexitatea este O(M*N) = O(N2) (folosindu-ne de propietatea 2). De altfel problema determinarii numarului de triunghiuri (clici de 3 noduri) intr-un graf, de aceasta data general, este cunoscuta si cea mai rapida rezolvare cunoscuta de noi este O(M*N / 32) daca pastram matricea de adiacenta pe biti - in total O(N2 / 32) memorie. Va lasam pe voi sa descoperiti aceasta solutie iar daca nu reusiti cereti ajutor pe forum si vom completa acest articol.
- In cazul clicilor de 4 noduri, tot ce avem de facut este sa selectam doua muchii si sa vedem daca cele 4 capete ale lor formeaza o clica (presupunda ca avem 4 capete distincte). Acest algoritm are complexitatea O(M2) = O(N2)
Cum determinam, rapid, daca doua noduri sunt vecine? Solutia cea mai usoara este sa pastram matricea de adiacenta (eventual pe biti) si putem raspunde in O(1) la astfel de intrebari dar memoria este O(N2). O alta idee care reduce marimea memoriei la O(M) este sa pastram listele de adicenta sub forma de hash-uri in loc de liste simple inlantuite (pentru cei care nu sunt familiari cu aceasta structura de date ii sfatuim sa citeasca articolele de pe devnet - sunt interesante si educative). Asadar, folosind hash-urile, memoria ramane O(M) dar putem afla rapid (aproape O(1)) daca doua noduri sunt vecine. In C++ aceasta structura de date este deja implementata sub numele de map, desi un query are complexitate logaritmica.
Sa trecem la solutia O(N). Evident, vom folosi propietatea 1 (singura nefolosita pana acum). Din moment ce avem un nod cu grad mai mic decat 6, il identificam, generam toate clicile care il contin printr-un backtracking (dat fiind faptul ca sunt maxim 5 vecini) si il scoatem din graf. Graful rezultat este si el planar si cautam iar nodul cu grad mai mic decat 6, etc. Evident, nu vom face cautarea nodului de fiecare data - asta ar duce la un O(N2), ci in momentul in care stergem un nod, verificam daca gradele vecinilor sai au scazut sub 6 si apelam o procedura recursiva cand gasim un astfel de vecin (un soi de DFS in graful dat). Dat fiind faptul ca backtracking-ul ruleaza in timp constant (desi e mare constanta) algoritmul acesta va avea complexitatea O(N) - presupunand ca putem raspunde in O(1) folosind hashurile daca doua noduri sunt vecine. Solutia noastra foloseste map-urile din STL asadar are complexitatea O(N*logN) cu o constanta considerabila (~100).
Solutia de mai sus suporta multiple optimizari asupra factorului constant daca efectuam niste prepocesari inainte de algoritmul descris. Asadar, putem prepocesa pentru toate grafurile de maxim 6 noduri in care exista un nod conectat la toate celelalte, care este clica maxima si cate sunt. Nu sunt mai mult de 212 asemenea grafuri, deci prepocesarea va rula instantaneu. Avand aceasta informatie prepocesata, cand eliminam un nod din graful planar, in loc sa facem backtracking pentru a afla clicile maximale, interogam tabelul cu valorile prepocesate, optimizand factorul constant foarte mult (ajunge ~6). Totusi, nu era necesara implementarea acestor optimizari, din moment ce problema era media setului.
Cowfood
(problema grea, clasele 11-12)
Problema este bazata pe principiul includerii si excluderii. Constrangerile relativ mici ale problemei nu ar fi trebuit sa va pacaleasca sa incercati o cautare exhaustiva, intrucat aceasta ar fi obtinut numai 20-30% din punctaj.
Inainte de a trece la explicarea problemei, sa ne amintim principiul includerii si excluderii.
|A1 U A2 U ... U An| =
|A1| + |A2| + ... + |An|
- |A1 ∩ A2| - |A2 ∩ A3| - ... (toate perechile)
+ |A1 ∩ A2 ∩ A3| + ... (toate tripletele)
...
+ (-1)(n-1) |A1 ∩ A2 ∩ ... ∩ An|
Cum va fi folosit acesta? Vom calcula solutia ca fiind |multimea tuturor experimentelor valide| - |multimea experimentelor valide care sigur vor esua|. Sa notam aceasta multime de experimente cu F. Pentru orice experiment X, vom nota fX = multimea tutoror experimentelor care vor esua conform experimentului X.
Astfel, pentru un experiment A de forma (a1, a2, ..., aK) si orice experiment B = (b1, b2, ..., bK) cu a1 ≤ b1, a2 ≤ b2, ..., aK ≤ bK, B apartine fA.
In acest moment putem sa ne dam seama de solutie
|F| = |fE1 U fE2 U ... U fEN|, care - conform principiului includerii si excluderii - este egal cu
|fE1| + |fE2| + ... + |fEN|
- |fE1 ∩ fE2| - |fE1 ∩ fE3| - ... (toate perechile)
+|fE1 ∩ fE2 ∩ fE3| ...(toate tripletele)
...
+(-1)n-1 |fE1 ∩ fE2 ∩ ... ∩ fEN|
Ce reprezinta intersectia ("∩") in acest context?
Daca A = (a1, a2, ..., aK) si B = (b1, b2, ..., bK), A ∩ B va fi multimea ce contine toate experimentele despre care se stie cu siguranta ca vor esua, atat conform lui A cat si lui B. Altfel spus, A ∩ B = multimea experimentelor care vor esua conform (max(a1, b1), max(a2, b2), ..., max(aK, bK)).
Un ultim lucru care trebuie obinut este calcularea lui |fX| pentru orice X = (x1, x2, ... xK). Pentru a obtine un experiment esuat, putem incrementa toate valorile xi atata timp cat suma lor este ≤ S. Astfel avem |fX| = m(S - (x1 + x2 + ... + xK), K), unde m(i, j) reprezinta numarul de posibilitati de a aranja cel mult i bile identice in j cutii diferite.
Aceasta se calculeaza simplu folosind recurenta care nu va fi demonstrata aici
m(i, j - 1) = p(i, j) = p(i - 1, j) + p(i, j - 1), i, j > 0
m(i, 0) = 1
m(0,j) = 1
cu p(i, j) = numarul de posibilitati de a aranja exact i bile identice in j cutii diferite. Valorile m(i, j) se preproceseaza la inceput intr-o matrice, in timp O(K*S).
O implementare bruta a problemei va duce la complexitatea O(K*S + 2N*N*K), dar aceasta ar obtine numai 60% din punctajul maxim. O implementare inteligenta folosind preferabil o functie recursiva care exploreaza toate submultimile celor N experimente si la fiecare pas actualizeaza solutia in O(K) obtine cu usurinta 100 de puncte. Complexitatea sa este O(K*S + 2N*K).
