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.

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.

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 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 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 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 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 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)

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

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)

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

Sponsori

Organizarea finalei preONI este posibila datorita generosilor nostri sponsori: