h3. (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:
== code(c) |
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':http://www.ginfo.ro/revista/11_2/focus2.pdf.
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{~1~} + A{~2~} + ... + A{~i~} = S{~i-1~}+A{~i~}$ si un al doilea sir $T{~i~} = max(S{~1~}, S{~2~},..., 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~}$.
Un alt mod de a verifica secventele de forma $i,i+1,...N-1,N,1,2,...j-1,j$ este daca observam ca suma acestei secvente este de fapt suma tuturor elementelor din care se scade secventa $j+1, j+2, ... i-2, i-1$. Astfel ne intereseaza o secventa de suma minima pe care sa o scadem din suma totala. Aceasta se poate determina cu o mica modificare a alogirtmului pentru suma maxima sau inmultind elementele cu $-1$ si cautand o secventa de suma maxima.
Complexitatea rezolvarii este $O(N)$, iar pentru reconstituirea solutiei sunt necesare doar cateva variabile aditionale pentru pozitie si lungime.
h2. 'Zero 2':problema/zero2
h3. (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{~1~}^e{~1~}^*p{~2~}^e{~2~}^*...*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{~1~})/e{~1~}], [Nr(N, p{~2~})/e{~2~}], ..., [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^2^]+[x/p^3^]+...$ care a fost prezentata si 'aici':http://infoarena.ro/preoni-2006/runda-4/solutii. Astfel:
$Nr(N, p) = [N/p]+[N/p^2^]+[N/p^3^]+... + [(N-1)/p]+[(N-1)/p^2^]+[(N-1)/p^3^]+... + [1/p]+[1/p^2^]+[1/p^3^]+... =$
$= [N/p]+[(N-1)/p]+...+[1/p] + [N/p^2^]+[(N-1)/p^2^]+...+[1/p^2^] + [N/p^3^]+[(N-1)/p^3^]+...+[1/p^3^] + ...$.
Fie $S(N, p) = [N/p]+[(N-1)/p]+...+[1/p]$. Putem scrie $Nr(N, p) = S(N, p) + S(N, p^2^) + S(N, p^3^) + ...$.
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{~p~}N)$.
h2. 'Puteri':problema/puteri
h3. (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^i^$} 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 construi 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^i^$}, 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$ numar prim. Cardinalul acestei reuniunii se va calcula folosind principiul includerii si excluderii:
==code(cpp) |
|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$}.
h2. 'Balanta':problema/balanta
h3. (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)$
h2. 'Expresii 2':problema/expresii2
h3. (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:
==code(cpp) |
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 ≤ i ≤ N-K$} avem relatiile:
Fie sigma o {$K$}-permutare cu $N$ elemente => pentru orice {$i$}, {$1 ≤ i ≤ 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 ≤ R < K$}.
Fie $N$ = {$C * K + R$}, {$0 ≤ 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 ≥ 2 * K$}, sau, echivalent {$C ≥ 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.
I. {$N ≥ 2 * K$}, sau, echivalent {$C ≥ 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 ≤ 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:
