Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2007-03-05 16:50:01.
Revizia anterioară   Revizia următoare  

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 Si = A1 + A2 + ... + Ai = Si-1+Ai si un al doilea sir Ti = max(S1, S2,..., Si) = max(Ti-1, Si). 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: Ti-1+SN-Si-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 = p1e1*p2e2*...*pkek. 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, p1)/e1], [Nr(N, p2)/e2], ..., [Nr(N, pk)/ek]).
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/p2]+[x/p3]+... care a fost prezentata si aici. Astfel:
Nr(N, p) = [N/p]+[N/p2]+[N/p3]+... + [(N-1)/p]+[(N-1)/p2]+[(N-1)/p3]+... + [1/p]+[1/p2]+[1/p3]+... =
= [N/p]+[(N-1)/p]+...+[1/p] + [N/p2]+[(N-1)/p2]+...+[1/p2] + [N/p3]+[(N-1)/p3]+...+[1/p3] + ....

Fie S(N, p) = [N/p]+[(N-1)/p]+...+[1/p]. Putem scrie Nr(N, p) = S(N, p) + S(N, p2) + S(N, p3) + ....
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(logp 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*logpN).

Puteri

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

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

In continuare vom arata un mod de a calcula cardinalul unei multimi multimi Ai. Se observa ca o pereche (a,b,c) (x,y,z) apartine multimii Ai 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 Ai 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 xi*j el se poate scrie si sub forma yi, unde y va fi chiar xj. Asadar Ai*j este inclusa in Ai. Deci ne va interesa reuniunea multimilor Ai 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 Ai 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 Ai cu i ≤ 128.

Balanta

(problema usoara, clasa a 10-a)

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. 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".

Ograzi

(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.

KPerm

(problema medie, clasele 11-12)

Fie sigma o K-permutare cu N elemente => pentru orice i, 1 ≤ i ≤ N-K avem relatiile:

  • sigmai + sigmai + ... sigmai+K-1 congruent cu 0 ( mod K )
  • sigmai+1 + sigmai+2 + ... sigmai+K congruent cu 0 ( mod K )

Scazand cele doua relatii, obtinem sigmai congruent cu sigmai+K ( mod 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 sigmai congruent cu sigmai+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:

  • 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 A0 = 1, pentru orice A. Deci demonstratia a fost facuta fara a restrange generalitatea.

Magazin

(problema grea, clasele 11-12)

Sponsori

Organizarea finalei preONI este posibila datorita generosilor nostri sponsori: