Solutii preoji 2017

• Lista de probleme
• Crescator1
• Sortare2
• Costuri
• Gard5
• Partii
• Evaluare1
• Nori
• Permheap
• Statiuni
• LuffXor

Crescator1

In primul rand, putem construi o functie ce calculeaza suma cifrelor unui numar in timp logaritmic prin implementarea urmatoarei formule recursive: suma_cifre(x) = 0, daca x = 0, sau x%10 + suma_cifre(x/10) altfel. Prin aceasta, daca cunoastem al i-lea numar al sirului al doilea, putem gasi urmatorul in timp logaritmic. Apoi, fie a[i] = primul sir, b[i] = al doilea sir. Observam ca b[1] > 0, si inductiv, b[i] > 0 si suma_cifre(b[i]) > 0, deci b[i] + suma_cifre(b[i]) > b[i], deci b[i+1] > b[i]. Astfel, sirul b este strict crescator. Pentru problema noastra sunt relevante doar elementele din b in care b[i] <= a[n]. Dar, b[1] = a[1], b[2] > b[1] = a[1], deci b[2] >= 1 + a[1]. Continuand pana la i, b[i] >= a[1] + i, dar, a[n] <= 300000 + a[1] (din ultima restrictie), deci a[n] <= b[300000], deci a[n] < b[300001]. Fie l = 300001. Astfel, doar elementele b[1], ..., b[l] sunt relevante. Le generam. Acum, trebuie doar sa aflam numarul de elemente din primul sir ce se gasesc in cel de-al doilea, cunoscand ambele siruri element cu element, si ca sirurile sunt in ordine sortata. Acest numar este egal cu numarul de elemente comune ale celor doua siruri. Putem gasi numarul acesta cu urmatoarea observatie: daca f(i) = j astfel incat b[j] >= a[i] > b[j-1], sau 1 daca un astfel de numar nu exista, atunci trebuie doar sa verificam daca a[i] = b[f(i)], pentru 1 <= i <= n, pentru a gasi toate elementele comune. Acum, observatia finala este ca f(j+1) >= f(j). f(1) = 1, caci a[1] = b[1], iar apoi calculam in O(n) valorile succesive ale lui f, memoizand rezultatele intermediare. Dupa, verificam de cate ori este adevarat ca a[i] = b[f(i)]. O optimizare ce nu reduce complexitatea este de a stoca mereu doar ultima valoare a lui f(i).

Sortare2

Observam ca la finalul etapei 1 nu putem avea valori neconsecutive pe pozitii consecutive in acelasi subsir (de exemplu 1 nu poate veni imediat inainte de 3 in acelasi subsir). Astfel, pentru o valoare i, ea poate fi fie sfarsitul subsirului sau, fie sa vina imediat inainte de i+1 in subsir, si ea poate fie sa fie primul element din subsir, fie sa vina imediat dupa i-1 in subsir. Astfel i si i+1 vor fi in subsiruri diferite daca si numai daca i vine (nu neaparat imediat) dupa i+1 in sirul initial. Putem, deci, sa numaram numarul de subsiruri prin a numara cate perechi de valori i, i+1 exista pentru care i vine (nu neaparat imediat) dupa i+1 in sirul initial. Numarul de operatii cerute este numarul acesta minus 1.

Costuri

In primul rand, putem construi o functie ce calculeaza produsul cifrelor unui numar in timp logaritmic prin implementarea urmatoarei formule recursive: prod_cifre(x) = x, daca x < 10, sau (x%10) * prod_cifre(x/10) altfel. Putem astfel sa gasim produsul cifrelor unui numar. Sa notam cu a sirul dat. Vom construi sirul cs = multimea {prod_cifre(a[i]) | 1 <= i <= n} sortata. Fie nc = lungimea lui c. Fie functia ind(cost) = pozitia lui cost in sirul cs, sau -1 daca cost nu se gaseste in cs, pe care o vom implementa printr-o cautare binara in sirul cs. Acum, vom mentine un sir de siruri vals, astfel incat vals[i] = sirul numerelor a[j], in ordinea din a, cu proprietatea ca ind(prod_cifre(a[j])) = i. Acesta il construim parcurgand sirul a si inserand fiecare element a[j] in parte in spatele sirului vals[ind(prod_cifre(a[j]))]. Acum, cand ni se cere sa gasim al p-lea numar cu costul c, mai intai verificam daca ind(c ) = -1; in cazul afirmativ, elemente cu costul c nu se gasesc in sir, si afisam -1. Altfel, ne uitam in vals[ind(c )]. Daca vals[ind(c )] are macar p elemente, atunci vals[ind(c )][p] este solutia; altfel afisam -1.

O solutie alternativa este posibila cu std::map din c++. Vom mentine un std::map<int, vector<int>> vals_, care va fi analog cu vals de mai inainte. Acum, in loc sa inseram/cautam in vals[ind(ceva)], vom insera/cauta direct in vals[ceva]. Inlocuirea std::map-ului cu un unordered_map nu ar modifica complexitatea, caci oricum este necesara o procesare in O(logn) pentru a afla costurile numerelor.

Gard5

Partii

Mai intai, pentru problemele de acest fel este deseori util sa creezi o "rama" in jurul matricii date, pentru a nu fi necesare verificarile de incluziune a unui indice in matrice. Astfel, notand matricea data cu A, definim A[ 0][i] = A[N+1][i] = A[i][ 0] = A[i][M+1] = inf, unde i este un indice corect in expresiile precedente, si inf e un numar mai mare ca oricare altul in matrice; practic, inf = 1000000000 + 1. Acum, definim d[i][j][sus/jos/dreapta/stanga] = lungimea celei mai lungi partii ce incepe in A[i][j], si se duce in sus/jos/dreapta/stanga. Vom descrie constructia lui d[i][j][sus], caci d[i][j][dreapta/stanga/jos] se construiesc analog. Trebuie avuta grija doar la ordinea iterarii. Implementam urmatoarea formula recursiva: d[i][j][sus] = d[i-1][j][sus] + 1 daca A[i][j] > A[i-1][j], altfel 1, pentru 1 <= i <= N si 1 <= j <= M. Pentru i = 0 sau i = N+1 sau j = 0 sau j = M+1, d[i][j] = 0. Acum, lungimea totala a partiilor ce pleaca din A[i][j] este d[i][j][sus] + d[i][j][jos] + d[i][j][stanga] + d[i][j][dreapta] - 3. Gasim i, j care maximizeaza aceasta expresie, si afisam valoarea ei in acest caz de maximalitate.

Evaluare1

Nori

Permheap

Observam, initial, ca structura unui heap este recursiva; subarborii care au ca radacina fiii radacinii unui heap reprezinta tot heap-uri. Astfel, avem ideea de a incerca o solutie folosind programarea dinamica. Fie sz[i] = marimea subarborelui heap-ului ce are ca radacina pe i, si d[i] = in cate moduri putem construi subarborele heap-ului ce are ca radacina pe i folosind valorile 1, 2, ..., sz[i], modulo 666013. Observam ca solutia problemei este d[ 1]. Acum, daca sz[i] = 1, atunci d[i] = 1, caci i este o frunza. Altfel, daca i are un singur fiu, fie el f, atunci d[i] = d[f], caci valoarea sz[i] trebuie sa fie asociata nodului i, iar toate modurile de a construi in rest subarborele lui i corespund cu moduri de a construi subarborele lui f. Acum, vom demonstra ca daca i are doi fii, fie ei f1, f2 , ca d[i] = d[f1] * d[f2] * C(sz[f1] + sz[f2], sz[f1]) modulo 666013, unde C(n,k) = combinari de n luate cate k. Valoarea nodului i este fixata; ea trebuie sa fie sz[i]. Acum, numarul de moduri de a distribui valorile ramase, adica 1, 2, ..., sz[f1] + sz[f2] la subarborii lui f1, f2 este egal cu C(sz[f1] + sz[f2], sz[f1]). Daca fixam distributia aceasta, numarul de moduri de a construi subarborele lui f1 este egal cu d[f1] (caci putem construi o bijectie intre modurile in care-l construim pe acest subarbore folosind valorile 1, 2, ..., sz[f1], si numarul de moduri de a-l construi folosind valorile fixate in pasul anterior); analog cu f2. Astfel, d[i] = d[f1] * d[f2] * C(sz[f1] + sz[f2], sz[f1]) modulo 666013. Tot ce ramane este calcularea rapida a lui C(n, k) modulo 666013. Stim ca C(n, k) = n! / (k! * (n-k)!), si 0 <= k <= n <= 200000. Astfel, trebuie sa precalculam i! modulo 666013 pentru 0 <= i <= 200000 si, cum 666013 e prim, putem calcula inversul modular al lui i! modulo 666013 folosind fie algoritmul lui euclid extins, fie mica teorema a lui Fermat impreuna cu exponentierea modulara in timp logaritmic. Notand inversul modular al lui i cu inv(i), C(n, k) = n! * inv(k!) * inv((n-k)!).

Statiuni

Frunzele arborelui reprezinta statiunile de pe plaja. Astfel, se cere numarul de noduri pentru care exista macar doua frunze la distanta nu mai mare de k fata de ele. Vom gasi lungimea celui mai scurt si al doilea celui mai scurt drum de la orice frunza la fiecare nod in parte. Daca ambele nu sunt mai lungi ca k, atunci nodul satisface conditia de mai sus, altfel nu. Vom calcula aceste valori cu un pseudo-bfs . Bfs-ul va incepe din frunzele arborelui, si va putea vizita fiecare nod de 2 ori. Prima data cand bfs-ul trece printr-un nod, el va actualiza lungimea drumului celui mai scurt de la oricare frunza la acel nod, iar a doua oara, el va actualiza lungimea drumului al doilea celui mai scurt de la oricare frunza la acel nod. Bfs-ul va actualiza coada de noduri mentinuta de bfs de fiecare data cand actualizeaza unul dintre drumurile unui nod. E important ca fiecare nod din coada sa retina nodul care a cauzat ca nodul acela sa fie adaugat la coada (nodul precedent in drum), pentru a evita drumuri de forma 1 -> 2 -> 1; in cazul nodurilor initiale, vom folosi valoarea unui nod inexistent. Din faptul ca un arbore este aciclic, aceasta precautie ne opreste din a vizita un nod de mai multe ori in acelasi drum. Demonstratia corectitudinii este similara cu cea a bfs-ului clasic: din multimea drumurilor posibile, noi exploram drumurile in ordinea lungimii lor, ignorand drumurile inutile (cele ce ar fi macar la fel de lungi ca al treilea cel mai scurt drum de la oricare frunza la un nod), si care nu ne ajuta in rezolvarea problemei (cele ce trec printr-un nod de macar 2 ori). Astfel, pseudo-bfs-ul ne gaseste lungimea celui mai scurt si al doilea celui mai scurt drum de la oricare frunza la fiecare nod in parte. Parcurgand toate nodurile, verificam cate au ambele aceste lungimi nu mai mari ca k; aceasta valoare reprezinta solutia.

Luffxor

Deseori cand avem de a face cu probleme cu operatii pe biti (in special xor) este util sa memoram numerele date sub forma unei trie a reprezentarilor binare a numerelor. Acum, fiecare nod din trie va mentine numarul de reprezentari binare ce "trec" prin nod (formal spus, au ca prefix sirul de caractere asociat cu nodul). Ca notatie, vom spune ca numarul de reprezentari binare ce "trec" prin n este n.nr. Memorand numerele in ordinea insertiei lor (pentru a stii care numar il stergem in operatia de tip 1), putem folosi tehnicile din problema trie sa rezolvam operatiile de tip 0, 1 cu complexitate O(n * lungimea sirurilor), adica O(nlogv), unde v = valoarea maxima a unui numar, mentinand valorile nr a tuturor nodurilor. Apoi, ramane doar operatia de tipul 3. In loc sa vedem cate numere y exista astfel incat x xor y <= k, vom vedea cate numere y exista astfel incat x xor y < k_ = k+1. Vom rezolva asta recursiv. Fie rad radacina trie-ului nostru. Sa ne uitam la rad. Daca bit-ul din k_ asociat nivelului lui rad este 0 atunci trebuie sa alegem fiul lui rad din care ar rezulta ca bitul corespunzator in x xor y sa fie 0 (unde y este orice reprezentare binara ce "trece" prin acel fiu), si sa continuam procedura recursiv, uitandu-ne la acel fiu. Altfel, daca bit-ul din k_ asociat nivelului lui rad este 1, atunci putem adauga din start la rezultat (fiul lui rad din care ar rezulta ca x xor y = 0).nr, unde y este orice reprezentare binara ce trece prin acel fiu, si continuam procesul recursiv cu celalalt fiu. Astfel, continuand procedura recursiv pana cand dam de un nod prin care "trec" 0 reprezentari binare, avem o procedura ce rezolva operatia de tipul 2 in O(adancimea unui nod), adica O(logv). Astfel, intreaga solutie da o complexitate adunata de O(nlogv).