• Home
• Clasament
• Organizatori
• Sponsori si premii
• Regulament
• Aparitii in presa
• Runde
• Runda 1
• Runda 2
• Runda 3
• Runda 4
• Runda Finala

Solutii Runda 3

Buline

(problema usoara, clasa a 9-a)

Problema este o variatie a unei probleme clasice: dandu-se un sir de N numere intregi sa se determine o secventa de suma maxima. Singura modificare este ca in aceasta problema sirul este circular. In prima parte a solutiei nu vom lua in considerare faptul ca sirul este circular. Pentru a rezolva problema pentru un sir normal exista o solutie clasica O(N). Se calculeaza pentru fiecare i secventa de suma maxima care se termina cu elementul i: este fie secventa de suma maxima care se termina la elementul i-1, la care se adauga elementul i, fie doar elementul i. O scurta descriere in pseudocod a acestui algoritm:

s = smax = 0;
pentru i = 1, n executa
   s = max(s+A[i], A[i]);
   smax = max(smax, s);
sfarsit pentru

O prezentare detaila a acestei probleme si metode de rezolvare gasiti aici.
Vom trata acum si faptul ca sirul este circular. Astfel, trebuie verificate si secventele de forma i,i+1,...N-1,N,1,2,...j-1,j. Pentru a realiza acest lucru eficient precalculam un sir de sume partiale S_i = A₁ + A₂ + ... + A_i = S_i-1+A_i si un al doilea sir T_i = max(S₁, S₂,..., S_i) = max(T_i-1, S_i). Pentru un i fixat, cea mai buna secventa de forma i,i+1,...N-1,N,1,2,...j-1,j se poate calcula in O(1) astfel: T_i-1+S_N-S_i-1. Complexitatea rezolvarii este O(N), iar pentru reconstituirea solutiei sunt necesare doar cateva variabile aditionale pentru pozitie si lungime.

Zero 2

(problema medie, clasa a 9-a)

Fie E(N) = 1!*2!*...*N!. Numarul de zerouri terminale in scrierea lui E(N) in baza B este egal cu numarul de ori E(N) se imparte la B. Pentru a determinarea puterea la care apare B in E(N) vom descompune numarul B in factori primi B = p₁^e₁*p₂^e₂*...*p_k^e_k. Fie Nr(N, p) puterea la care apare numarul prim p in descompunerea in factori primi a lui E(N). Rezultatul va fi min([Nr(N, p₁)/e₁], [Nr(N, p₂)/e₂], ..., [Nr(N, p_k)/e_k]).
Asadar problema se va reduce la a calcula Nr(N, p) in mod eficient. O prima rezolvare de complexitate O(N*lg N) este de parcurge toate numerele de la 1 la N si de a determina puterea la care apare p in x! (1 ≤ x ≤ N) folosind formula [x/p]+[x/p²]+[x/p³]+... care a fost prezentata si aici. Astfel:
Nr(N, p) = [N/p]+[N/p²]+[N/p³]+... + [(N-1)/p]+[(N-1)/p²]+[(N-1)/p³]+... + [1/p]+[1/p²]+[1/p³]+... =
= [N/p]+[(N-1)/p]+...+[1/p] + [N/p²]+[(N-1)/p²]+...+[1/p²] + [N/p³]+[(N-1)/p³]+...+[1/p³] + ....

Fie S(N, p) = [N/p]+[(N-1)/p]+...+[1/p]. Putem scrie Nr(N, p) = S(N, p) + S(N, p²) + S(N, p³) + ....
Vom arata in continuare ca se poate calcula S(N, p) in O(1) astfel:
Termenii [1/p],[2/p]...[(p-1)/p] au valoarea 0
Termenii [p/p],[(p+1)/p]...[(2*p-1)/p] au valoarea 1
Termenii [(2*p)/p],[(2*p+1)/p]...[(3*p-1)/p] au valoarea 2
...
Termenii [(k*p)/p],[(k*p+1)/p]...[((k+1)*p-1)/p] au valoarea k
Termenii [((k+1)*p)/p]...[N/p] au valoarea k+1
Astfel k = [N/p]-1 iar S(N, p) = k*(k+1)/2*p + (k+1)*(N-(k+1)*p+1). Putem acum calcula Nr(N, p) in O(log_p N). Factorizarea numarului B se poate face in O(√B), iar numarul mediu al factorilor primi din descompunerea lui B este ln ln B, complexitatea finala a rezolvarii fiind O(√B + lnlnB*log_pN).

Puteri

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

Notam A_i multimea perechilor al caror produs se scrie sub forma xⁱ cu x numar natural. Problema ne cere calcularea cardinalului reuniunii multimilor A_i.

In continuare vom arata un mod de a calcula cardinalul unei multimi A_i. Se observa ca o pereche (a,b,c) (x,y,z) apartine multimii A_i daca a+x=0,b+y=0 si c+z=0 (mod i). Vom constui un tablou Nr[r1][r2][r3] care reprezinta numarul de triplete (x,y,z) cu proprietatea r1=x,r2=y,r3=z (mod i). Vom adauga la cardinalul multimii A_i produse de forma Nr[a][b][c]*Nr[i-a][i-b][i-c] (i-a,i-b,i-c se calculeaza tot mod i). Deasemenea trebuie avut grija la numerele pentru care 2*a=0 2*b=0 si 2*c=0 (mod i), deoarece trebuie adunat Nr[a][b][c]*(Nr[a][b][c]-1)/2 pentru a nu numara aceeasi pereche de mai multe ori.

O observatie care ne va ajuta sa calculam cardinalul reununiunii este faptul ca daca un numar se scrie de forma x^i*j el se poate scrie si sub forma yⁱ, unde y va fi chiar x^j. Asadar A_i*j este inclusa in A_i. Deci ne va interesa reuniunea multimilor A_i pentru i produs de numere prime. Cardinalul acestei reuniunii se va calcula folosind principiul includerii si excluderii:

|S| = |A[2]| + |A[3]| + |A[5]| + ...
    - |A[6]| - |A[10]| - |A[15]| + ...
    + |A[30]| + ...
    - ...

Cardinalul multimii A_i se adauga la solutie in cazul in care i are un numar impar de divizori primi si se va scadea din solutie daca are un numar par de divizori. Termenii pentru care in descompunerea lui i apare un factor la putere mai mare de 1 vor fi ignorati. Datorita limitarilor din enunt nu va trebui sa verificam decat multimile A_i cu i ≤ 128.

Balanta

(problema usoara, clasa a 10-a)

Problema se rezolva mentinand doua multimi H si L continand monedele candidate pentru moneda mai grea, respectiv cele candidate pentru moneda mai usoara. Initial H si L contin fiecare toate elementele multimii {1..N}. Cele doua multimi se vor actualiza dupa fiecare cantarire. Notand cu A multimea monedelor asezate pe bratul stang si cu B multimea monedelor asezate pe bratul drept al balantei, vom proceda in felul urmator:

• talerele sunt echilibrate - este clar ca nici una din monedele din A sau B nu poate fi mai grea/mai usoara, deci H va deveni H - A - B, iar L va deveni L - A - B

• talerul stang este mai greu - moneda falsa, in caz ca este mai grea, se va afla cu siguranta in multimea A sau, in caz ca este mai usoara, se va afla in multimea B. Astfel, H devine H ∩ A, iar L devine L ∩ B

• talerul drept este mai greu - caz simetric cu cel anterior, H devine H ∩ B, iar L devine L ∩ A.

La final vom avea solutie daca si numai daca |H| = 1 si |L| = 0, caz in care moneda falsa este mai grea, sau |H| = 0 si |L| = 1, cand moneda falsa este mai usoara.

Complexitatea algoritmului care rezolva problema este O(M*N)

Expresii 2

(problema grea, clasa a 10-a)

Problema se rezolva folosind programarea dinamica. Mai intai calculam o matrice V, unde V[i, j] reprezinta numarul de sfarsituri valabile de expresii ce se pot forma ce necesita adaugarea a j variabile la inceput pentru a se forma o expresie corecta de lungime i. Relatiile de recurenta se determina usor urmarind cu atentie in ce configuratii putem ajunge din configuratia actuala (putem pune o variabila, +, * sau !).
Rezolvarea celei de-a 2-a parti a problemei implica folosirea matricei V. Avand valorile calculate putem afla caracterul pe care trebuie sa il punem pe o anumita pozitie. Este evident ca la fiecare pas indicele expresiei cautate scade cu numarul de expresii peste care "sarim".

O alta solutie este determinarea expresiei cu numarul P caracter cu caracter folosind o functie care determina cate expresii de o lungime fixata exista care incep cu un prefix dat (prefixul fiind un sir de caractere). Pentru a implementa eficient acesta functie se memoizeaza rezultatele intermediare folosind o tabela hash. Prezentam o scurta descriere a acestei proceduri in pesudocod:

intreg numara(lungime, prefix)
   daca numara(lungime, prefix) a mai fost apelat returneaza rezultatul stocat in hash; 
   daca lungime = 1 si prefix = "" returneaza K;
   daca lungime = 1 si prefix = "A" sau "B" ... sau "Z" returneaza 1;
   daca lungime = 1 returneaza 0; 
 
   rez = 0;
   daca |prefix| < lungime sau (|prefix| = lungime si prefix se termina cu "!")
      rez += numara(lungime-1, prefix[1..lungime-1]);

   daca |prefix| < lungime sau (|prefix| = lungime si prefix se termina cu "*")
      pentru i = 1, n-2 executa
         rez += numara(i, prefix[1..i])*numara(n-i-1, prefix[i+1..n-i-1]);

   daca |prefix| < lungime sau (|prefix| = lungime si prefix se termina cu "+")
      pentru i = 1, n-2 executa
         rez += numara(i, prefix[1..i])*numara(n-i-1, prefix[i+1..n-i-1]);

   pastreaza valoarea rez in hash pentru numara(lungime, prefix);
   returneaza rez;
sfarsit functie
|

h2. 'Ograzi':problema/ograzi

h3. (problema usoara, clasele 11-12)

Problema este una clasica de cautari ortogonale si se poate face usor o solutie in care se sorteaza dreptunghiurile si punctele dupa coordonata $x$, iar apoi se foloseste o linie de baleiere. Se proceseaza updateuri si querieruri pe un arbore de intervale in o dimensiune. Aceasta solutie are complexitate $O(M*lg N + N*lg N)$. S-au obtinut in jur de $70$ de puncte folosind asemenea abordari.
Pentru a obtine o solutie mai eficienta trebuia exploatata particularitatea problemei, adica faptul ca toate dreptunghiurile erau egale. Solutia autorului continea doi pasi: 

* Intai folosim grila de puncte de coordonate $(i*W+0.5, j*H+0.5)$ unde $i$ si $j$ sunt numere intregi. Orice dreptunghi din enunt contine exact un punct din aceasta grila. Vom folosi o tabela de dispersie (hash) ce grupeaza in perechi dreptunghiurile din intrare si punctele din grila interioare lor. 
* Pentru a determina daca un punct din cele $M$ este continut in vreun dreptunghi, ne uitam care sunt cele patru puncte din grila vecine acestuia, si vom gasi maxim patru dreptunghiuri asociate acelor 4 puncte din grila. Apoi testam incluziunea punctului nostru in fiecare dintre cele patru dreptunghiuri, astfel putem raspunde la orice test de incluziune in $O(1)$. 

Complexitatea toatala a algoritmului este $O(N + M)$. Felicitam pe Berzan Constantin care a folosit aceasta abordare si a fost singurul ce a luat punctaj maxim pe aceasta problema.

h2. 'KPerm':problema/kperm

h3. (problema medie, clasele 11-12)

Fie $sigma$ o {$K$}-permutare cu $N$ elemente => pentru orice {$i$}, {$1 &le; i &le; N-K$} avem relatiile:

* {$sigma{~i~} + sigma{~i~} + ... sigma{~i+K-1~}$} congruent cu $0$ ( mod $K$ )
* {$sigma{~i+1~} + sigma{~i+2~} + ... sigma{~i+K~}$} congruent cu $0$ ( mod $K$ )

Scazand cele doua relatii, obtinem $sigma{~i~}$ congruent cu $sigma{~i+K~}$ ( mod {$K$} ).
Fie $N$ = {$C * K + R$}, {$0 &le; r < K$}.
Se observa ca intr-o {$K$}-permutare nu conteaza decat resturile numerelor la impartirea cu $K$, si nu numerele propriu-zise. Deci putem privi o permutare in functie de cate resturi r sunt in permutare, pentru orice {$r$} de la $0$ la {$K-1$}. Se observa ca resturile de la $1$ la $R$ apar de exact {$C+1$} ori, in timp ce toate celelalte resturi apar de exact $C$ ori.

I. {$N &ge; 2 * K$}, sau, echivalent {$C &ge; 2$}. Se observa ca in primele $C$ numere din permutarea care constituie o solutie nu putem pune acelasi rest de cel putin $2$ ori. Observatia este evidenta, deoarece, cum avem relatia $sigma{~i~}$ congruent cu $sigma{~i+K~}$ ( mod {$K$} ), atunci restul care ar aparea de 2 ori in primele $C$ numere ar aparea de cel putin {$2*C$} ori ( pe primele {$C*K$} pozitii ), dar avem maxim {$C+1$} resturi disponibile egale, si cum {$2*C > C+1$}, am ajuns la o contradictie.
II. {$K &le; N < 2*K$}. In acest caz, resturile de la $1$ la $R$ apar de $2$ ori fiecare, iar toate celelalte resturi apar o singura data. Cum doar pozitiile de la $R+1$ la $C$ au un rest unic in permutare ( toate celelalte resturi apar pe exact doua pozitii de forma $i$ si $i + K$ ) => pe aceste pozitii trebuie sa punem toate resturile care apar o singura data. Este evident si ca in primele $R$ pozitii trebuie sa punem resturile diferite doua cate doua, pentru ca fiecare rest apare de doua ori si trebuie pus pe doua pozitii.

Din ambele cazuri a rezultat ca pentru orice valori ale numerelor $N$ si $K$, o {$K$}-permutare trebuie sa respecte urmatoarele proprietati: 

* pe primele $K$ pozitii din permutare trebuie sa se gaseasca toate resturile {$0$}, {$1$}, ... {$K-1$}
* resturile de la $1$ la $R$ trebuie sa fie asezate pe primele $R$ pozitii
* pe fiecare pozitie $i$ incepand cu $K+1$ trebuie sa punem un numar care sa aiba restul din impartirea la $K$ egal cu restul impartii numarului de pe pozitia $i-K$ la {$K$}

Pentru $K$ par, {$K = 2p$}, cum {$0+1...+(2p-1)$} = {$p*(2p-1)$} si acest numar nu se divide cu {$2p$} pentru ca {$2p-1$} este impar => raspunsul este 0.

Pentru $K$ impar, {$K = 2p+1$}, cum {$0+1...+2p$} = {$p*(2p+1)$}, care este dizibil la {$(2p+1)$}, vom construi permutarea astfel:

* fixam ordinea primelor $R$ resturi ( in total {$R!$} variante )
* fixam ordinea celorlalte $K-R$ resturi ( in total {${@(K-R)!@}$} variante )
* pentru fiecare rest din primele $R$ sunt $C+1$ pozitii pe care trebuie sa il asezam. Pentru fiecare rest putem pozitiona numerele atasate in {$(C+1)!$} variante, si, cum sunt $R$ resturi, avem {$[(C+1)!]^R^$} variante
* pentru fiecare din celelalte resturi sunt $C$ pozitii pe care trebuie sa le asezam. Pentru fiecare rest putem deci pozitiona numerele atasate in {$C!$} variante, si, cum sunt $K-R$ resturi, avem {$(C!)^K-R^$} variante.

Pentru $K$ impar raspunsul este, dupa cum am demonstrat mai sus, {$(R!)$} * {${@(K-R)!@}$} * {$[(C+1)!]^R^$} * {$(C!)^K-R^$}.

OBS. In relatia de mai sus nu are importanta daca {$R = 0$}, caci {$0! = 1$} si {$A^0^ = 1$}, pentru orice {$A$}. Deci demonstratia a fost facuta fara a restrange generalitatea.


h2. 'Magazin':problema/magazin

h3. (problema grea, clasele 11-12)

Problema se rezolva folosind metoda programarii dinamice, dar 


==Include(page="template/preoni-2007/footer")