==
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~}$. Complexitatea rezolvarii este $O(N)$, iar pentru reconstituirea solutiei sunt necesare doar cateva variabile aditionale pentru pozitie si lungime.
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~}$.
h2. 'Zero 2':problema/zero2
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.
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$.
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)
h3. (problema grea, clasele 11-12)
Problema se rezolva folosind metoda programarii dinamice. Ca prim pas vom precalcula niste informatii pentru fiecare culoar care vor fi folosite apoi in algoritmul de programare dinamica. Astfel pentru un culoar $i$ exista 4 scenarii care ne intereseaza:
* se face un pas de distanta $D$ din coltul de sus al unui culoar adiacent la coltul de sus al culoarului $i$, se iau toate produsele de pe culoar incepand de sus si se revine la coltul de jos al culoarului $i$
* se face un pas de distanta $D$ din coltul de sus al unui culoar adiacent la coltul de sus al culoarului $i$, se iau toate produsele de pe culoar incepand de sus si se revine la coltul de sus al culoarului $i$
* se face un pas de distanta $D$ din coltul de jos al unui culoar adiacent la coltul de jos al culoarului $i$, se iau toate produsele de pe culoar incepand de jos si se revine la coltul de jos al culoarului $i$
* se face un pas de distanta $D$ din coltul de jos al unui culoar adiacent la coltul de jos al culoarului $i$, se iau primele $k$ produse de pe culoar incepand de jos si se revine la coltul de jos al culoarului $i$, se face un pas de distanta $D$ din coltul de sos al unui culoar adiacent la coltul de sos al culoarului $i$, se ia restul de produse de pe culoar incepand de sus si se revine la coltul de sus al culoarului $i$
Se observa ca primul tip de scenariu (cat si cel simetric) are mereu un cost constant, si anume $D+M+1$. Asadar, se vor precalcula informatii doar pentru ultimele 3 tipuri. Aceste informatii se pot calcula usor sortand produsele de pe fiecare culoar si parcurgandu-le (in cazul ultimului scenariu). Complexitatea acestui pas este $O(P*lgP + N)$.
Vom realiza acum algoritmul de programare dinamica construind traseul optim culoar cu culoar, de la $1$ la $N$. Se observa ca exista $6$ stari care ne intereseaza la un culoar $i$:
* $0$ - costul unui traseul optim care trece prin coltul de sus al culoarului $i$, fara a trece prin coltul de jos al culoarului $i$
* $1$ - costul unui traseul optim care trece prin coltul de sus al culoarului $i$, care trece prin coltul de jos al culoarului $i$, iar traseul este conex
* $2$ - costul unui traseul optim care trece prin coltul de sus al culoarului $i$, care trece prin coltul de jos al culoarului $i$, iar traseul *nu* este conex, adica este format din doua trasee care se vor uni la un moment dat (la un culoar $> i$)
* $3$ - costul unui traseul optim care trece prin coltul de jos al culoarului $i$, fara a trece prin coltul de sus al culoarului $i$
* $4$ - costul unui traseul optim care trece prin coltul de jos al culoarului $i$, care trece prin coltul de sus al culoarului $i$, iar traseul este conex
* $5$ - costul unui traseul optim care trece prin coltul de jos al culoarului $i$, care trece prin coltul de sus al culoarului $i$, iar traseul *nu* este conex, adica este format din doua trasee care se vor uni la un moment dat (la un culoar $> i$)
Pentru a calcula oricare din cele $6$ stari ne uitam la cele $6$ stari ale culoarului $i-1$. In total, vor exista $6*6 = 36$ de tranzitii; fiecare se poate calcula in $O(1)$ folosind informatiile precalculate la primul pas. Cele $36$ de tranzitii se pot determina usor pe foaie, trasand cateva exemple. Complexitatea acestui pas este $O(N)$, deci rezolvare este in final $O(P*lg P + N)$.
==Include(page="template/preoni-2007/footer")==
