Solutii - Concurs de selectie a echipelor ACM ICPC, UPB 2008

• Lista de probleme
• Rest
• Dictree
• Exit
• G2mm
• Ksecv
• Maxunice
• Mm
• Per
• Pkinv
• Pp

Rest

Problema se reduce la gasirea unei structuri care sa permita rezolvarea celor doua tipuri de operatii. Putem folosi un arbore de intervale A, unde un nod reprezinta restul impartirii la P a numarului format din alipirea cifrelor in baza B din intervalul corespunzator. Constructia arborelui se poate face recursiv: A[i] = (A[fiu_stanga] * B^{lungime_interval_fiu_dreapta} + A[fiu_dreapta]) % P. Pentru a face o operatie de tipul 1 (update), modificam frunza corespunzatoare operatiei si actualizam arborele recursiv dinspre frunza spre radacina. La o operatie de tipul 2 (query), intervalul dat il spargem intr-un numar minim de intervale consecutive ce apar si in arbore. Rezultatul pentru un query, se face din compunerea acestor intervale, dupa aceeasi formula de recurenta.
Pentru a obtine complexitatea O(logN) atat pe operatia query, cat si pe update, este necesara precalcularea puterilor lui B modulo P.

Dictree

Problema se reduce la gasirea numarului de noduri ale trie-ului format din cuvintele din dictionar. Cu toate aceastea, limita de memorie restransa nu permite construirea efectiva a trie-ului. Pentru a rezolva problema, putem sorta lexicografic cuvintele din dictionar si sa vedem cate noduri "aduce" fiecare cuvant fata de cel precedent lexicografic. Este usor de observat ca acest numar este egal cu diferenta dintre lungimea cuvantului curent si lungimea celui mai lung prefix comun al celor doua cuvinte. Complexitatea solutiei este O(N*logN*Lmax), unde Lmax este lungimea maxima a unui cuvant.

Exit

G2mm

In primul rand trebuie mentionat faptul ca va exista intotdeauna un cuplaj perfect in acest graf, lucru care va reiesi din algoritmul prezentat in continuare. Vom nota graful din intrare cu G iar graful patrat cu G^2. Vom creea un arbore partial al grafului G, pentru asta putem folosi un DF sau un BF. Avand arborele il vom parcurge de jos in sus (de la frunze catre radacina) si vom creea cuplajul astfel: Pentru fiecare nod consideram sirul F₁, F₂, F₃ .. F_N unde F_i este un fiu al nodului curent care nu a fost inca introdus in cuplaj. Daca acest sir are numar impar de noduri atunci introducem si nodul curent in sir, acesta avand acum un numar par de elemente. Acum cuplam pur si simplu aceste noduri din sir (e usor de gasit o astfel de modalitate) avand in vedere ca in G^2 aceste noduri vor avea toate muchii intre ele. Exista intotdeauna solutie deoarece graful are un numar par de noduri si este conex.

Ksecv

Maxunice

O observatie destul de intuitiva este ca pentru a avea cat mai multe numere in rezultat, acestea trebuie sa fie cat mai mici. Astfel, solutia va fi de forma unui sir de numere consecutive care incepe cu 1, cu proprietatea ca suma elementelor din sir este ≤ N. Pentru a obtine suma exact N, vom mari ultimul termen din sir.

Mm

Per

Cea mai rapida solutie se bazeaza pe hashing. Pentru aflarea rezultatului vom construi o dinamica A[i][j] = numarul de secvente de lungime i concatenate care se termina in j.
Formula de recurenta este usor de dedus :

• Daca la pasul i,j sirul care incepe pe i-j+1 este identic cu cel de pe i-2j+1 atunci A[i][j] = A[i][j-i]+ 1
• alfel A[i][j] = 1;

Pentru a afla in O(1) daca doua siruri sunt egale vom construi H[i][j] = (ch[i] - 'a') * prim[ 1 ] + (ch[i+1] - 'a') + prim[ 2 ] + .. + (ch[j] - 'a' * prim[j-i+1] ) unde prim[i] va fi al i-lea numar prim si ch[i] este caracterul de pe pozitia i.

Desi nu in toate cazurile un hash ar da o solutie corecta aici este putin probabil sa apara 2 valori identice pentru siruri diferite.
La fiecare pas cand intalinim un A[i][j] >= K adunam la rezultat.

Pentru a se incadra in memorie este necesar sa mentinem doar ultima linie a matricii pentru hash si dinamica.
Compexitatea finala este O(N^2) ca timp si O(N) ca memorie. 

Pkinv

Problema este asemanatoare cu problema Perm6 si ne duce cu gandul, in prima faza, la o dinamica de forma c[i][j] = numarul de permutari de i elemente cu j inversiuni. Recurenta iese usor, gandindu-ne cu cat creste numarul de inversiuni in functie de ultimul numar adaugat in permutare: c[i][j] = c[i-1][j] + c[i-1][j-1] + ... + c[i-1][max(j-i+1, 0)]. Din pacate, aceasta dinamica are complexitatea O(N*K²). Desi dinamica se poate reduce la complexitate O(N*K) folosind sume partiale, ar insemna sa ne indepartam ca idee de solutia optima a problemei. Observam in dinamica de mai sus, ca pentru K < i ≤ N, functia max va returna mereu valoarea 0, deci recurenta nu mai variaza in functie de i. Astfel, putem considera trecerea de la pasul i la pasul i+1 o inmultire de matrici:
.
Folosind proprietatea de asociativitate a inmultirii matricilor, putem deduce:
.
Inmultirea a doua matrici K x K are complexitate O(K³), iar ridicarea la putere are nevoie de O(logN) astfel de inmultiri. Pentru a calcula dinamica pana la pozitia K+1, putem aplica recurenta de mai sus avand o complexitate O(K³). Complexitatea finala este O(K³*logN).

Pp