Solutii Algoritmiada 2009, Runda 2

• Lista de probleme
• Marmote
• Ejoc
• Bazaconii
• Colier
• Papuci
• Nrsec
• Jap

Marmote

Se observa ca o vizuina are forma unui romb cu centrul in punctul X_i, Y_i. O prima solutie de complexitate O(N*M + K*L²) este urmatoarea: vom mentine o matrice Fol[i][j] in care vom marca pozitiile care apartin vreunei vizuine. In momentul in care soseste o noua marmota vom verifica in O(L²) daca toate pozitiile vizuinei sale nu sunt folosite de alta marmota, iar in caz afirmativ vom marca pozitiile noii vizuini in matrice.
Observatia necesara pentru a reduce complexitatea este ca daca avem doua vizuini care se intersecteaza, atunci pentru fiecare din cele doua vizuini cel putin unul din cele patru varfuri este o pozitie comuna. Astfel, putem sa verificam in O(1) daca o anumita marmota poate sa isi construiasca vizuina uitandu-ne doar la cele patru varfuri. Pentru a obtine o solutie corecta trebuie sa avem grija la vizuinele care se afla pe marginile campului. Va trebui sa extindem matricea Fol astfel incat sa cuprinda in totalitate vizuinile. Complexitatea acestei solutii este O(N*M + K).

Ejoc

Jocul se aseamana foarte tare cu algoritmul lui Euclid prin scaderi. Stim ca daca avem doua numere A si B si tot scadem din cel mai mare pe cel mai mic, pana cand numerele devin egale, numerele la sfarsit o sa fie egale cu cmmdc(A, B) (cel mai mare divizor comun). Aici cu siguranta se va ajunge la un moment dat sa se obtina cmmdc(A, B), si apoi acest cmmdc(A, B) va putea fi scazut in mod repetat din A sau din B. Cum jocul se termina cand nu se mai poate efectua nici o mutare se observa ca la sfarsit se vor obtine toti multiplii lui cmmdc(A, B) pana in A sau in B. Rezulta ca numarul de mutari nu depinde de mutarile jucatorilor ci doar de A si B, si acesta este max(A, B) / cmmdc(A, B) - 2. Castigatorul este deci determinat doar de paritatea numarului de mutari posibile.

Bazaconii

Prima observatie pe care o putem face este ca putem rezolva problema independent pentru fiecare bit al numerelor. Vom numi vecini doua numere din sir daca intre ele exista o relatie prin care este cunoscuta suma lor xor. Daca pentru al i-lea numar din sir setam al j-lea bit 0 stim ca pentru toti vecinii lui i bitul j este fortat la una din cele doua valori posibile (ecuatiile 0 xor x = 0 si 0 xor x = 1 au solutii unice). Acelasi lucru se intampla si daca setam al j-lea bit 0. Odata ce am setat bitii pentru vecinii lui i putem seta si biti pentru vecinii vecinilor lui i si asa mai departe. Practic vom folosi o coada in care vom introduce intai al i-lea numar apoi vom scoate mereu din coada un numar caruia i-am setat bitul si daca vecinii sai nu se afla deja in coada ii vom introduce si pe acestia. Pentru a obtine solutia minim lexicografica vom incerca mereu sa alegem numarul cu indicele cel mai mic care nu a fost deja preprocesat si daca atat 0 cat si 1 furnizeaza o solutie valida vom seta bitul la valoarea 0. La sfarsit mai trebuie sa verificam daca toate conditiile se respecta. Mai simplu decat sa verificam pentru fiecare bit in parte este sa observam ca daca exista solutie, atunci daca fixam un numar din sir pe valoarea 0 va exista si in acest caz o solutie.

Colier

Se observa destul de usor ca starea de castigare pentru N = 2 este 01 sau 10. Acum sa vedem ce se intampla cand avem un colier cu N > 2 perle. In primul rand trebuie sa avem cel putin o perla 1. De fiecare data cand alegem un 1, putem sa avem vecinii 0 1 0, 0 1 1, 1 1 0, 1 1 1. Putem observa ca in urma unei astfel de operatii paritatea perlelor 0 ramane aceeasi. De aici tragem concluzia ca numarul de perle 0 trebuie sa fie impar (pentru ca la un moment dat trebuie sa ajungem in una din starile castigatoare pentru N = 2). Tot la fel de usor se observa ca sigur exista o secventa de alegeri care sa ne duca la sfarsit, daca avem numar impar de perle 0 (singurul caz particular ar fi cand avem doar trei perle 1 una langa alta si o alegem pe cea din mijloc, atunci ramanem fara perle 1, dar daca alegem de fiecare data o perla 1 care are cel putin un vecin 0 sigur o sa fie totul bine, si cum trebuie sa existe cel putin o perla 0 sigur putem face aceasta alegere). De aici solutia iese foarte usor. Aveti grija, exista cateva cazuri particulare usoare, pe care va las sa le descoperiti singuri :).

Papuci

Observam ca daca privim capatul din stanga al unei perechi ca o paranteza deschisa si capatul din dreapta ca o paranteza inchisa obtinem defapt un sir de parantezari valide. De asemenea daca inversam doua litere dintr-o pereche observam ca sunt afectate doar parantezarea care incepe exact dupa capatul din dreapta al perechii, parantezarea care incepe exact dupa capatul din stanga al perechii si cea care se termina exact inainte de capatul din dreapta al perechii (evident daca acestea exista). Vom rezolva problema cu ajutorul programarii dinamice. Sa presupunem ca avem o pereche x care are in interiorul ei perechile a₁ a₂ ... a_k care corespund unor alte parantezari corecte: ( a₁ a₂ ... a_k ). Vom calcula Min[ x ][ 0 ] ca fiind costul minim care se obtine pentru perechea x daca nu interschimbam caracterele si Min[ x ][ 1 ] costul minim care se obtine daca interschimbam parantezele. Acest cost se calculeaza luand in calcul doar ce se intampla in interiorul perechii de paranteze x. Pentru a calcula aceasta valoare am avea nevoie de valorile Min[ a₁ ][ 0 ], Min[ a₁ ][ 1 ], Min[ a₂ ][ 0 ], Min[ a₂ ][ 1 ] .... Apoi trebuie sa facem o noua dinamica in care vom calcula o matrice Cmin[ 2 ][ 2 ] in care prima valoare indica faptul daca am interschimbat sau nu caracterele din perechea a₁ si a doua valoare daca am interschimbat sau nu caracterele din perechea a₂. Putem calcula aceasta matrice in timp liniar. Dupa ce am calculat toate valorile Min[ i ][ 0 ] si Min[ i ][ 1 ] putem calcula raspunsul final luand in calcul numai relatiile care nu sunt incluse in alte relatii (vom avea un sir de genul (..)(..)(..)). Complexitatea pentru a calcula toate valorile necesare din dinamica este O(N), deoarece o pereche o accesam doar atunci cand calculam valorile pentru perechea de paranteza ce o include pe ea, dar numai pentru prima dintre acestea. Se pot obtine 100 de puncte si cu solutii de complexitate O(N*logN) care folosesc o sortare pentru a determina sirul de parantezari.

Nrsec

Primul pas in rezolvarea acestei probleme este sa vedem ca S poate fi cautat binar. Fie NR[S] numarul de subsecvente a caror suma este mai mica sau egala cu S. NR[S] este crescator in functie de S, cand creste S, creste si NR[S] deci S poate fi cautat binar. Ce ramane de facut este avand un S sa aflam NR[S]. Pentru ca numerele pot fi si negative sumele subsecventelor care se termina intr-un anumit punct nu sunt neaparat crescatoare, trebuie sa gasim o solutie care sa nu tina cont de asta.
O solutie este asa: facem sumele partiale A[i] = suma primelelor i numere din sir. Acum suma unei subsecvente i - j este A[j] - A[i - 1]. Sortam aceste sume tinand pentru fiecare si indicele ei. Parcurgem sumele sortate in ordine. Sa presupunem ca suntem la pozitia i. Vrem sa numaram cate subsecvente cu capatul in i au suma mai mica sau egala cu S. Fie j celalat capat al acestor subsecvente. J trebuie sa respecte A[j] - A[i - 1] ≤ S. Se poate usor observa ca j poate fi de la o anumita pozitie incolo in sirul sortat si daca i creste, j poate doar sa creasca. Explicatie: sa presupunem ca sirul de sume partiale este : -1, 1, 5, 6 si S = 2. Daca i = 1, j poate fi de la 1 spre sfarsit, daca i = 2, j poate fie de la 1 spre sfarsit, daca i = 3, j poate fi de la 3 spre sfarsit, daca i = 4, j poate fi de la 4 spre sfarsit. J poate fi astfel usor determinat in timp ce parcurgem vectorul cu i in O(N). Avand j pentru fiecare i putem deduce ca numarul subsecventelor care se au un capat in i si a caror suma este mai mica sau egala cu S este N - j + 1 (unde N este numarul elementelor din sir). Dar daca adunam toate aceste valori observam ca unele subsecvente le numaram de doua ori. Ca sa evitam acest lucru putem sa numaram doar pozitiile j care apar ca indice din vectorul initial (nesortat) inaintea lui i. Pentru aceasta putem folosi un arbore de intervale, sau un arbore indexat binar (orice structura care poate sa faca update si query pe un interval in O(log N)). La inceput in acesta tinem toate pozitiile posibile, si pe masura ce j creste scoatem pozitiile din spatele lui j. La pozitia i facem query pe intervalul 1...PI[i] (unde PI[i] este pozitia sumei partiale i inainte de sortare).
O alta solutie se bazeaza pe algoritmul merge sort si este asemanatoare cu modul de numarare a numarului de inversiuni dintr-o permutare. Va las pe voi sa va ganditi cum :).
Complexitatea acestor algoritmi in total este: O(N * log N * log S_MAX) (unde S_MAX este suma maxima a unei subsecvente)

Jap

Vom considera toate numerele naturale intre 2 si N inclusiv care nu pot fi scrise sub forma x^y, unde y diferit de 1. Notam aceasta multime cu numere S. Pentru fiecare din aceste numere vom calcula puterea maxima la care poate fi ridicat astfel incat rezultatul sa fie ≤ N. Pentru un numar i, vom considera ca aceasta putere este j (deci i^j ≤ N) si vom incerca sa calculam cate elemente distincte se pot genera ridicand fiecare din elementele i¹, i², i³, ..., i^j la puteri intre 1 si M. Astfel pentru i va trebui sa calculam cate elemente distincte are secventa i¹, i², ..., i^M, i^2*1, i^2*2, ..., i^2*M, ..., i^j*1, i^j*2, ..., i^j*M. Observam ca oricum am alege x si y din multimea S, secventele generate cu regula de mai sus vor fi complet disjuncte, si in plus reuniunea tuturor secventelor va constitui intreaga secventa data in enunt. Astfel, suma numarului de elemente distincte determinate pentru fiecare x din S va reprezenta numarul cerut in enunt.

Setul S poate fi determinat, parcurgand elementele de la 2 la N si marcand toate puterile mai mari ca 1 al elementului curent ca nefacand parte din set. Determinarea setului S are complexitate O(N).

De aici putem elabora mai multe solutii de complexitati diferite:

• O(N) precalculare, O(N * M * log(N * M)) pe test - 20 de puncte

Pentru fiecare i din S, calculam j, cel mai mare numar natural astfel incat i^j ≤ N, adaugam puterile 1, 2, 3, ..., M, 2, 4, 6, ..., 2M, ..., j, 2j, 3j, ..., jM intr-un vector, il sortam si adunam la rezultat numarul de elemente distincte din el.

• O(N) precalculare, O(N log N) pe test - 50 de puncte

Pentru fiecare i, vom calcula numarul de elemente distincte din secventa corespunzatoare lui folosind principiul includerii si excluderii. Fie A un subset al multimii [1, 2, 3, ..., j]. Vom calcula comun[A] = numarul de puteri aflate in intersectia tuturor secventelor (x*1, x*2, x*3, ..., x*M), pentru x apartinand lui A. Intersectia acestor secvente trebuie sa contina numai elemente ≤ M * min(A), unde min(A) = elementul minim din subsetul A, si numai elemente divizibile cu lcm(A), unde lcm(A) reprezinta cel mai mic multiplu comun al elementelor din A. Astfel comun[A] va fi egal cu [M * min(A) / lcm(A)], unde [x] reprezinta partea intreaga a lui x.

Acum, conform principiului includerii si excluderii. putem determina numarul de elemente distincte ale secventei corespunzatoare lui i, adunand comun[A] pentru toate subseturile A avand numar impar de elemente si scazand comun[A] pentru toate subseturile A avand numar par de elemente.

Observam ca pentru multe numere din setul S, puterea maxima j la care poate fi ridicat astfel incat rezultatul sa fie ≤ N se repeta si vom calcula comun[A] de multe ori pentru aceleasi subseturi. Pentru a evita acest lucru putem calcula valorile lui comun la inceput, pentru orice subset al multimii [1, 2, 3, ..., log₂ N] si mentine rez[x] = numarul de elemente distincte din secventa generata de un element i din S pentru care puterea maxima este egala cu x.

Complexitatea totala devine O(2^{log N} log N)) precalcularea lui comun + O(N) adunarea sumelor, deci O(N log N).

• O(N + nr_M_distinct * N log N) precalculare, O(N) pe test - 70 de puncte

Observam ca valorile lui comun si rez depind doar de M si deci le putem calcula doar pentru fiecare M diferit din fisierul de intrare.

• O(N + nr_M_distinct * N log N) precalculare, O(log² N) pe test - 100 de puncte

Am observat deja ca daca 2 numere diferite i si j din setul S au aceeasi putere maxim j la care pot fi ridicate fara sa depaseasca N, numarul de elemente distincte din secventa generata de fiecare dintre ele este egal.

In loc sa parcurgem toate elementele din S, putem numara pentru fiecare putere j de la 1 la log₂ N cate numere din S au aceasta putere maxima. Pentru fiecare putere putem determina limitele sale inferioare si superioare prin cautare binara si, precalculand nrInS[i] = cate numere naturale ≤ i sunt in setul S, putem determina cate elemente sunt in S intre cele 2 limite. Complexitate finala pe test O(log² N).

Observatie

Este posibil sa ajungem la un query time de O(1).
Astfel, sa presupunem ca pentru fiecare putere pana in logN stim cate duplicate sunt generate de un numar care este putere maxima.
( exemplu: pentru exponentul egal cu 4, stim ca avem x duplicate. Atunci daca inmultim numarul de numere care sunt puteri la a patra ( 16, 81, etc ) cu x o sa avem numarul de duplicate date de puterile la a patra. Daca facem asta pentru fiecare putere p pana in logN, si adaugam la rezultat, obtinem rezultatul query-ului pentru un N dat.
In primul rand, pentru fiecare n <= N si p <= logN, putem precalcula cate puteri la a p-a sunt <= n, in O( N log N ). De asemenea, putem
preprocesa fiecare query posibil in O(N log N) [ nu avem decat sa stocam produsul "cate puteri la a p-a sunt <= n" * "cate duplicate sunt pentru p"].
Tinand cont ca O(N log N) necesitam oricum pentru fiecare M distinct, ajungem la un query time de O(1).

Sper ca s-a inteles :)

Solutie alternativa

A doua solutie calculeaza care sunt puterile i pentru care uⁱ poate fi scris ca v^j cu v < u si j ≤ M. Prima conditie pe care trebuie sa o indeplineasca u, este sa se scrie de forma p₁^f1 * ... * p_t^ft unde cmmdc(f₁, ..., f_t) = d, d ≠ 1. Daca notam w radicalul de ordin d al lui u, atunci uⁱ se va scrie ca w^d*i, ba chiar mai mult se va scrie ca (w^q)^i*d/q unde q divide d.
Pornind de la aceste observatii putem calcula pentru un M fixat cate numere distincte generaza (w^d)ⁱ pentru fiecare d in parte ( d este maxim log₂N, adica 16). (w^d)ⁱ se poate scrie in functie de w^q cu q < d, daca i e divizibil cu q/cmmdc(d, q), adica i*d multiplu al lui cmmmc(d, q). Asadar pentru fiecare d intre 2 si 16 si q intre 1 si d, vom insemna intr-un tablou ca puterea k*cmmmmc(d, q), unde k * cmmmc(d, q) / q <= M este duplicat pentru orice u = w^d.
Acum mai trebuie sa calculam pentru toate valorile de la 1 la N care este cmmdc-ul puterilor factorilor (adica d). Aceasta se poate face foarte repede sub forma asemanatoare cu ciurul lui Eratostene, numerele care au d > 1 pot fi scrise ca un numar mai mic ridicat la o putere si in loc sa adunam, inmultim.
Cu acest algoritm calculam dintr-o data toate query-urile care au acelasi M.
Complexitatea finala este O(nr_M_distinct * (M log² N + N log N)). O implementare atenta a acestei solutii va lua 100 de puncte.