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.
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!
h2. Numarare triunghiuri
h3. (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).
Numarare triunghiuri
Acum putem rezolva problema in $O(N^3^)$ 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.
(problema simpla, clasa a 9a)
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(N^2^ log N)$ si ar fi luat fara probleme punctajul maxim.
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).
Putem imbunatati solutia de mai sus la o complexitate {$O(N^2^)$}, eliminand cautarea binara. Aceasta solutie va lasam sa o descoperiti voi.
Acum putem rezolva problema in O(N^3) 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.
h2. Divizori primi
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(N^2 log N) si ar fi luat fara probleme punctajul maxim.
h3. (problema medie, clasa a 9a)
Putem imbunatati solutia de mai sus la o complexitate O(N^2), eliminand cautarea binara. Aceasta solutie va lasam sa o descoperiti voi.
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 {$ndp{~i~}$} - 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 $sol{~i,j~}$ care retine care este cel mai mare numaru 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 {$sol{~i,ndp{~i~}~}=i$}.
Pentru mai multe detalii despre cum functioneaza ciurul lui Erathostene puteti accesa "articolul":http://infoarena.ro/Ciurul_lui_Erathostene.
h2. Subsir 2
Divizori primi
h3. (problema grea clasa a 9a, problema medie clasa a 10a, problema usaora clasele 11-12)
(problema medie, clasa a 9a)
Problema poate fi considerata asemanatoare cu cea a celui mai lung subsir crescator, avand o rezolvare similara de complexitatea $O(N^2^)$ folosind metoda programarii dinamice.
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 ndp[i] - 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 sol[i][j] care retine care este cel mai mare numaru 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 sol[i][ndp[i]]=i.
Pentru mai multe detalii despre cum functioneaza ciurul lui Erathostene puteti accesa articolul:
[1]http://info.devnet.ro/articole.php?page=art&art=30
Subsir 2
(problema grea clasa a 9a, problema medie clasa a 10a, problema usaora clasele 11-12)
Problema poate fi considerata asemanatoare cu cea a celui mai lung subsir crescator, avand o rezolvare similara de complexitatea O(N^2) folosind metoda programarii dinamice.
Se vor construi doi vectori:
A[i] = lungimea celui mai scurt subsir crescator maximal care incepe cu pozitia i
T[i] = urmatorul element dupa pozitia i in cel mai scurt subsir crescator maximal care incepe cu i (pentru reconstiutire)
* $A{~i~}$ = lungimea celui mai scurt subsir crescator maximal care incepe cu pozitia $i$
* $T{~i~}$ = 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 V[i] <= V[j] (unde V este vectorul de numere) si se alege acela cu A[j] minim, A[i] devenind A[j]+1, iar T[i] devine j. Daca nu exista nici un j, A[i] se initializeaza cu 1 si T[i] cu i.
Pentru fiecare {$i$}, se va cauta un $j > i$ astfel incat {$V{~i~} ≤ V{~j~}$} (unde $V$ este vectorul de numere) si se alege acela cu $A{~j~}$ minim, $A{~i~}$ devenind {$A{~j~}+1$}, iar $T{~i~}$ devine {$j$}. Daca nu exista nici un {$j$}, $A{~i~}$ se initializeaza cu $1$ si $T{~i~}$ 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 V[i] <= V[k] <= V[j], 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(N^3) care ar fi adus 50-60p. Pentru a face verificarea in O(1), facem observatia ca ne intereseaza doar acel V[k] minim care este >= V[i]. Pe masura ce se avanseaza cu variabila j, se pastreaza o variabila min, reprezentand minimul dintre valorile V[j]parcurse pana acum, care sunt >= V[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 {$V{~i~} ≤ V{~k~} ≤ V{~j~}$}, 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(N^3^)$ care ar fi adus {$50-60p$}. Pentru a face verificarea in {$O(1)$}, facem observatia ca ne intereseaza doar acel $V{~k~}$ minim care este ≥ {$V{~i~}$}. Pe masura ce se avanseaza cu variabila {$j$}, se pastreaza o variabila {$min$}, reprezentand minimul dintre valorile $V{~j~}$ parcurse pana acum, care sunt ≥ {$V{~i~}$}.
Astfel, cand se ajunge la un j, se verifica inainte daca V[j] < 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 A[j] minim, in caz de egalitate se va alege acela cu valoarea V[j] minima. Selectarea este corecta deoarece nu vor exista j1, j2 cu A[j1] si A[j2] minim , iar V[j1] = V[j2].
Problema se poate rezolva mai bine intr-o complexitate O(N*lg^2 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.
Astfel, cand se ajunge la un {$j$}, se verifica inainte daca {$V{~j~} < 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 $A{~j~}$ minim, in caz de egalitate se va alege acela cu valoarea $V{~j~}$ minima. Selectarea este corecta deoarece nu vor exista {$j1$}, $j2$ cu $A{~j1~}$ si $A{~j2~}$ minim , iar {$V{~j1~} = V{~j2~}$}.
Problema se poate rezolva mai bine intr-o complexitate $O(N*lg^2^ 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.
h2. Sum
h3. (problema usoara, clasa a 10a)
Sum
(problema usoara, clasa a 10a)
Vom face o prima observatie:
* $(n, d) = 1 <=> (n, n - d) = 1, (n, n + d) = 1 $
(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 {$x{~1~}, x{~2~}, .. x{~a~}$} numerele $< n$ si prime cu $n$ => numerele cuprinse intre $n$ si $2 * n$ si prime cu $n$ vor fi {$x{~1~} + n, x{~2~} + n, .. x{~a~} + n$}.
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 x(1), x(2), .. x(a) numerele < n si prime cu n => numerele cuprinse intre n si 2 * n si prime cu n vor fi x(1) + n, x(2) + n, .. x(a) + n.
Conform observatiei facute, $(n, n - x{~1~}) = 1, (n, n - x{~2~}) = 1, .. (n, n - x{~a~}) = 1$ =>
Conform observatiei facute, (n, n - x(1)) = 1, (n, n - x(2)) = 1, .. (n, n - x(a)) = 1 =>
x{~a~} = n - x{~1~} <=> x{~1~} + x{~a~} = n
x{~a-1~} = n - x{~2~} <=> x{~2~} + x{~a-1~} = n
x(a) = n - x(1) <=> x(1) + x(a) = n
x(a-1) = n - x(2) <=> x(2) + x(a - 1) = n
...
x{~1~} = n - x{~a~} <=> x{~a~} + x{~1~} = n
x(1) = n - x(a) <=> x(a) + x(1) = 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 :
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$}.
[2]http://info.devnet.ro/articole.php?page=art&art=30
$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":http://infoarena.ro/Ciurul_lui_Erathostene despre cirulul lui Erathostene.
O alta solutie, propusa de Bogdan A. Stoica, se bazeaza pe principul includerii si excluderii. Din enuntul problemei ne dam seama ca suma ceruta este suma tuturor numerelor z cu proprietatea ca cmmdc(z, x) = 1. Pentru a afla aceste numere este de ajuns sa observam ca cmmdc(z, x) != 1 daca si numai daca exista cel putin un pi = qj unde z = p1^e1*...*pn^2n, iar x = q1^f1*....*qm^fm. Fie doua astfel de numere pi = qj. Noi trebuie sa afla suma tuturor numerelor care se divid cu pi si sunt in intervalul [0, 2*x]. Aceste numere sunt : pi, 2*pi, ..., k*pi, 0 < k <= [2*x/pi]. Suma acestor numere se poate scrie ca pi +....+ k*pi, adica pi(1+...+k) adica pi*k(k+1)/2. De aici suntem tentati sa credem ca suma ceruta (fie aceasta S) este S = x(2*x-1) - p1*k1*(k1+1)/2 - .... - pn*kn*(kn+1)/2. La o citire mai atenta observam ca am scazut unele
de doua ori (cele care se divid si cu p1 si cu p2, de exemplu) si nu am scazut deloc alte numere care au un divizor comun cu x mai mare decat 1 (cele care se divid simultan cu p1, p2 si p3, de exemplu). Astfel, aplicand principiul includerii si excluderii putem schita formula finala : S = x*(2x-1) - p1*k1*(k1+1)/2 - ... + p1*p2*k'1(k'1+1)/2 + ... - p1*p2*p3*k''1(k''1+1)/2 + ..., adica vom scadea toti termenii care se obtin prin inmultirea a unui numar impar de factori primi si vom aduna restul. Aceasta solutie obtine in jur de 80 de puncte pe restul testelor depasind timpul de executie.
