solutie/nrchei

Solutia problemei NrChei

Mai intai vom face cateva observatii legate de o rezolvarea problemei chei, iar apoi vom vedea cum putem aplica ideile obtinute la problema noastra.

Sa presupunem ca in inputul problemei Chei se afla sirul S.

S e un sir periodic de perioada minima P, cu |P| = K, K * T = |S|. Perioada unui sir e orice sir pe care daca il concatenez cu el insusi de zero sau mai multe ori, obtin sirul initial. Perioada minima e cea mai scurta dintre ele, si este unica pentru un sir dat.

Prima observatie e ca de acum e suficient sa ne uitam la numarul de perechi de chei care se pot confunda din P. Aceasta se datoreaza faptului ca daca in orice perioada a lui S, doua chei nu se pot distinge, atunci nici daca il dublez, sau il triplez, samd., tot nu voi putea distinge intre ele. Mai mult, daca am o pereche de chei pe care am reusit sa o disting intr-o perioada lui S, voi putea distinge intre cele 2 chei pe intregul sir. Pentru a valida aceste 2 afirmatii, ne putem folosi de intuitie, gandindu-ne la un inel de chei, sau le putem verifica sub incidenta rezolvarii deja cunoscute a problemei. Ce mai e de observat acum e ca am ales sa vorbim totusi de perioada minima, pentru cauze ce vor fi in curand analizate, dar argumentul este independent de minimalitatea ei.

Sa presupunem ca P are A perechi de chei care se confund. Numarul total de astfel de perechi, in S, este:

$K \frac{T(T-1)}{2} + AT^2$ - aceasta e valoarea pe care trebuie sa o egalam cu n

Primul termen este expresia matematica a faptului ca o cheie aflata pe pozitia q in S formeaza pereche de chei confundabile cu orice cheie aflata la o pozitie r pentru care

$q &\equiv r \pmod{K}, q \neq r$

Aceasta se datoreaza periodicitatii. In plus, cel de-al doilea termen provine din faptul ca daca am o pereche de chei confundabile in P, fiecare dintre ele formeaza o pereche (in plus fata de cea explicata mai sus) - cu corespondentul modulo K al perechii sale initiale - pentru fiecare din cele T aparitii disjuncte ale lui P in S. Alte perechi nu mai sunt care sa merite numarate, deci formula e corecta. Ramane de vazut cum o vom folosi.

Merita sa analizam cum depinde A de felul in care arata P. Cand vom folosi termenul de rotatie a unui sir, ne vom referi la rotatii circulare, adica aplicarea succesiva a mutarii primului element din sir la capatul sau. Stim ca P e neperiodic (un sir e neperiodic atunci cand perioada sa minima e chiar el insusi) (altfel, am fi gasit o perioada mai scurta, contrazicand minimalitatea lui P), deci pentru a avea macar o pereche de chei confundabile, singura varianta e sa putem roti sirul in asa fel incat sa contina un palindrom de marime cel putin K - 1. Orice astfel de sir se poate roti in asa fel incat sa respecte unul din cele 4 cazuri:

indicele categoriei	relatii intre valorile sirului $P_0 \ldots P_{K - 1}$	conditii impuse asupra lui $K$	valoarea lui `A` in general	exemple de $P$	valoarea lui `A` in exemplu
$\Lambda$	$P_i = P_{K - i}, \forall i \in \{ 1, 2, \ldots, K - 1 \}$	$K$ impar	`A =` $\frac{K - 1}{2}$	xabccba, xabaaba	`3`
$\Omega$	$P_i = P_{K - i}, \forall i \in \{ 1, 2, \ldots, K - 1 \}$	$K$ par	`A =` $\frac{K}{2} - 1$	babcacba = acbababc, xabcycba, xabcxcba, xabxxxba	`3`
$\Gamma$	$P_i = P_{K - i - 1}, \forall i \in \{ 0, 1, \ldots, K - 1 \}$	$K$ par	`A =` $\frac{K}{2}$	abcddcba	`4`
$\Xi$	$non \Lambda, non \Omega, non \Gamma$	-	`0`	abcdef	`0`

Sirul neperiodic P trebuie doar sa respecte relatiile date, pentru macar o rotatie de-a sa, pentru a se incadra definitiv intr-una din categorii. E clar ca orice sir face parte din cel mult o categorie. Din fericire, periodicitatea si rotirea sunt probleme foarte asemanatoare cand vine vorba de numarare de siruri, dupa cum vom vedea.

O observatie pe care o putem face de pe acum, care ne va ajuta mai incolo, e sa vedem ca de vreme ce A e aproximativ $\frac{K}{2}$ (cu exceptia ultimei categorii), deci din formula care leaga A, K si T de n, deducem ca -T * (K + 1) ≤ n - T² * (K + 1) ≤ 0

Nota. Acum deja va puteti raspunde la intrebarea, in caz ca v-a trecut asa ceva prin minte, cum se pot face teste ne-banale la problema chei? Folosindu-ne de aceste observatii, putem sa ne asiguram ca o solutie care ia puncte, le ia pe deplin pe merit: palindroame lungi, scurte, din toate cele 3 categorii (desigur, separat), rotite si concatenate prezinta suficient material pentru un set teste decisiv. Poate nu e asa interesant la prima vedere, dar acest aspect a stat la bazele cercetarilor care au dat nastere acestei probleme.

Numim sir canonic orice sir neperiodic care nu are nevoie de nicio rotatie circulara pentru a respecta conditiile din categoria sa. Sa notam cu $\alpha(k)$ , $\beta(k)$ , $\gamma(k)$ si $\xi(k)$ numarul de siruri canonice, neperiodice de k caractere dintr-un alfabet de marime $\Sigma$ , pentru care sirul sa se incadreze in categoria $\Lambda$ , $\Omega$ , $\Gamma$ , respectiv $\Xi$ . De exemplu, sirul bcycbaxa este numarat in $\frac{k}{2} \beta(n)$ prin faptul ca xabcycba e numarat in $\beta(n)$ . Pentru simplitatea explicatiei, si pentru a evidentia carcterul general al calculelor, vom nota cu $\Theta, \chi$ pentru a ne referi la oricare dintre $\Lambda, \alpha$ , $\Omega, \beta$ , $\Gamma, \gamma$ , respectiv $\Xi, \xi$ . (Tinem a nota ca cele ce urmeaza vor fi mult mai clare, mai usor de dedus si de inteles pentru cei care vor analiza niste exemple contextual generice de siruri de marimi 20, respectiv 21.)

Atunci cand ne propunem sa calculam $\chi(k)$ , impunem constrangerile impuse de categoria [Unparseable or potentially dangerous LaTeX formula! Error 5 : 1020x1320] si vedem cum putem numara sirurile respective. Mai intai, sa observam ca orice sir canonic se poate roti circular de $\varkappa = \{ \Labmda : k, \Omega, \Gamma : \frac{k}{2}, \Xi : 1 \}$ ori, obtinand de fiecare data un alt sir. Intr-adevar, daca ar fi 2 siruri identice printre aceste rotatii, sirul nu ar avea cum sa fie neperiodic. Dintre acestea, doar el este canonic. Aceasta pentru ca sunt cel mult doua pozitii care sa fie centrul unui palindrom circular de marime cel putin k - 1, iar dintre ele deja am ales ca pozitie canonica pe exact una: pentru k impar, singura pozitie candidat e $0$ ; pentru k par, pozitiile $0$ si $\frac{k}{2}$ sunt ambele corecte.

Dar toate acestea nu inseamna decat ca e suficient sa gasim numarul de siruri canonice, $\chi(k)$ , pe care apoi sa il inmultim cu numarul corespunzator $\varkappa$ , pentru a afla numarul total de siruri din categoria respectiva. Putem pleca de la ideea ca orice sir care respecta conditiile din tabel este canonic, doar ca trebuie sa fie, in plus, periodic. Deci tot ce ne ramane de facut e sa scadem din numarul total atatea siruri care au, pe deasupra, perioada minima de lungime d, unde d este un divizor al lui k, pentru fiecare astfel de divizor.

Daca notam cu $\Upsilon_{\Theta}(k)$ numarul de siruri canonice periodice si neperiodice de marime k care respecta relatiile din categoria $\Theta$ , daca eventual le-am supune unei rotatii, vedem ca:

$\Upsilon_{\Lambda}(k) = \Sigma^{\frac{k + 1}{2}}$
$\Upsilon_{\Omega}(k) = \Sigma^{\frac{k}{2}}$
$\Upsilon_{\Gamma}(k) = \Sigma^{\frac{k}{2} + 1}$
$\Upsilon_{\Xi}(k) = \Sigma^{k}$

Sa investigam ce inseamna ca un sir sa fie periodic, dar, ignorand pentru o clipa restrictia aceasta din definitie, canonic! Pentru k impar, stim ca orice d e, la randul sau, impar. De asemenea, $\frac{k}{d}$ e impar. Cu aceste observatii in minte, si suprapunand conditiile ca sirul sa fie atat periodic, cat si de categoria $\Lambda$ , putem observa ca e vorba de exact sirurile numarate de $\alpha(d)$ , concatenate unul dupa altul, pana se obtine marimea k! Aceasta inseamna ca e suficient sa scadem $\alpha(d)$ din numarul total de solutii, si nu mai trebuie sa ne ingrijoram de sirurile cu perioada d!

Pentru k par, povestea se repeta! Perioada pastreaza categoria sirului mare, asa ca e suficient sa scadem $\chi(d)$ din $\chi(k)$ . In general, observam ca:

$(*): $ $\chi(k) = \Upsilon_{\Theta}(k) - \sum_{d = 1, d | k}^{k - 1} \chi(d)$

Pentru a calcula numarul de siruri din ultima categorie, de fapt vom calcula in $\chi(k)$ numarul total de siruri neperiodice, iar la final vom scadea cate fac parte din celelalte categorii, si anume: $k \alpha(k)$ (daca k e impar) sau $\frac{k}{2} (\beta(k) + \gamma(k))$ (daca k e par)

Pana acum am facut suficiente observatii ca sa putem trece la partea algoritmica a rezolvarii problemei. O prima idee de solutie ar fi sa calculam desigur sirul s_i = restul impartirii lui $\delta(k)$ la MOD. Acum am putea fixa K, si in caz ca e par, am fixa si valoarea lui A, am cauta valoarea lui T pentru care ecuatia care il leaga de n sa se respecte si am deduce tot ce avem nevoie din tabelul s. In functie de abordarea calculului, solutia va obtine intre 20 (ar fi un lowerbound pentru orice idee decenta) si (aproximativ) 75 de puncte:

O metoda bruta ar fi sa calculam sirul s pana la valoarea lui 2n + 2, folosind o metoda patratica de a verifica toti divizorii unui numar. Cautarea lui T se face in cel mai banal fel posibil. Calculul valorilor lui $\Sigma^{h}$ , atunci cand sunt cerute, in $O(h)$ . Daca cineva, in timpul unei runde lungi, se incapataneaza sa ajunga cu rationamentul aici si sa nu faca un pas spre a-si optimiza codul, sper ca nu va lua un punctaj mai mare decat il merita...
Sunt multe feluri de a imbunatati solutia precedenta: Putem precalcula puterile lui $\Sigma$ , il putem cauta pe T in $O(log(n))$ sau in $O(1)$ , amortizat sau nu. Putem gasi divizorii unui numar cu un algoritm mai eficient, sau putem chiar folosi ciur pentru a determina valorile din sirul s.
Pasul important catre solutia de 100 de puncte il constituie observatia ca numarul de numere mai mari ale caror valori in sirul s sunt interesante pentru noi este foarte scazut, si putem folosi memoizare pentru calculul acestora. O observatie care poate fi de folos aici e ca T divide 2n, prin urmare putem incerca divizorii sai, pentru care cautam valori K, A pentru care exista o sansa sa se potriveasca in ecuatie, iar apoi calculam valorile relevante din s pentru a actualiza raspunsul. Pentru un punctaj mai mare, putem calcula prin ciur valorile necesare pana la o anumita valoare, 10.000 sa zicem, si doar pentru celelalte memoizam.

Se cade sa facem un scurt rezumat al aventurii noastre cu aceasta problema. Am facut observatii legate de relatia intre forma sirului de caractere si numarul de perechi de chei care nu pot fi distinse. Am analizat aspecte ale numararii sirurilor neperiodice, sub incidenta proprietatilor care ne intereseaza. Am fost uimiti sa vedem cum toate se leaga, valorile pe care voiam sa le calculam se foloseau, in chip neasteptat, de ele insele, inlesnind drumul de la recurenta la solutie. Mai mult, am fost surprinsi sa vedem cat de mult se simplifica operatiile, ajungand sa retinem intr-un sir de numere tot ce ne-ar putea interesa. Apoi am cautat solutii eficiente de a implementa solutia, folosindu-ne de forma ecuatiei care leaga parametrii de numarul din input. A fost un tur de forta care ne-a trecut prin multe observatii, multe idei ad-hoc, si am ajuns, intr-un final, la un algoritm simplu, eficient, sprijinit pe multimea observatiilor facute, care exploateaza materie relativ redusa si tehnici deloc complicate (valabil si pentru solutia de mai jos).

Frumos este ca surprizele pregatite de aceasta problema nu se termina aici. Putem obtine un algoritm si mai eficient, care sa obtina scorul de 100 de puncte, daca mai facem o observatie. Formula (*) sugereaza ca exista o sansa sa aflam valorea lui $\chi(k)$ fara sa fie nevoie sa calculam valorile $\chi(d)$ . Sa analizam, mai exact, care este factorul, notat cu f(), cu care trebuie adunat $\Upsilon_{\Theta}(d)$ la raspuns, pentru fiecare d. De exemplu, daca k = 2 * 3 * 5 sa zicem, putem vedea ca $f(\Upsilon_{\Theta}(2 * 3 * 5)) = 1$ , $f(\Upsilon_{\Theta}(2 * 3)) = f(\Upsilon_{\Theta}(2 * 5)) = f(\Upsilon_{\Theta}(3 * 5)) = -1$ , $f(\Upsilon_{\Theta}(2)) = f(\Upsilon_{\Theta}(3)) = f(\Upsilon_{\Theta}(5)) = 1$ , respectiv $f(\Upsilon_{\Theta}(1)) = -1$ . Acest fenomen se generalizeaza in felul urmator:

Fie k = p₀^a₀ * p₁^a₁ * ... * p_r-1^a_r-1, descompunerea in factori primi a lui k
$f(\Upsilon_{\Theta}(d = p_0^{b_0} p_1^{b_1} \ldots p_{r-1}^{b_{r-1}})) = (-1)^{\sum a_i - \sum b_i}$ , orice d pentru care, oricare ar fi i, fie b_i = a_i, fie b_i = a_i - 1
$f(\Upsilon_{\Theta}(d = p_0^{b_0} p_1^{b_1} \ldots p_{r-1}^{b_{r-1}})) = 0$ , orice d pentru care exista i astfel incat b_i ≤ a_i - 2

Aceste observatii contureaza algoritmul pe care il vom implementa. Atunci cand e nevoie sa aflam valoarea lui $\chi(k)$ , il descompunem pe k in factori primi si, prin backtracking sau nu, pentru fiecare numar mask intre 0 si 2^r - 1 vom obtine divizorul pentru care b_i = a_i - bool(2ⁱ `and` mask) si vom aduna la rapuns $(-1)^{popcount(mask)} \Upsilon_{\Theta}(d)$ . In acest fel, nu mai e nevoie nici de recursivitate, nici de memoizare, nici de ciur, deoarece putem afla pe loc (in urma unei descompuneri in factori primi si a 2^r ridicari la putere in timp logaritmic) valorile cautate.

infoarena informatica de performanta

Solutia problemei NrChei