Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2007-03-05 16:47:39.
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 scrie si de forma yi unde y va fi chiar xj. Asadar Ai*j este inclusa in Ai. Deci ne va interesa reuniunea multimilor Ai pentru i numar prim. 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 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: