solutie/nrchei

Pagini recente » Cod sursa (job #2476426) | Rezultatele filtrării | Borderou de evaluare (job #1998379) | Rezultatele filtrării | solutie/nrchei

Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2020-03-28 23:27:20.
Revizia anterioară Revizia următoare

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 3 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 \}, P_0 \neq P_{\frac{K}{2}}$	$K$ par	`A =` $\frac{K}{2} - 1$	babcacba = acbababc, xabcycba	`3`
$\Gamma$	$P_i = P_{K - i}, \forall i \in \{ 1, 2, \ldots, K - 1 \}, P_0 = P_{\frac{K}{2}}$	$K$ par	`A =` $\frac{K}{2}$	xabcxcba, xabxxxba	`4`

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}$ , 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.

Sa notam cu $\alpha(k)$ , $\beta(k)$ si $\gamma(k)$ numarul de siruri neperiodice de k caractere dintr-un alfabet de marime $\Sigma$ , pentru care (sa existe o rotatie in asa fel incat) sirul sa se incadreze in categoria $\Lambda$ , $\Omega$ , respectiv $\Gamma$ . De exemplu, sirul bcycbaxa este 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$ , respectiv $\Gamma, \gamma$ . Numim sir canonic orice sir neperiodic care nu are nevoie de nicio rotatie circulara pentru a respecta conditiile din categoria sa. Cu ocazia aceasta, impunem categoriilor $\Omega$ si $\Gamma$ ca sirul canonic corespunzator sa respecte conditia ca $P_0 \ldots P_{\frac{k}{2} - 1} < P_{\frac{k}{2}} \ldots P_{k - 1}$ , din punct de vedere lexicografic (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 k ori, obtinand de fiecare data un alt sir. Intr-adevar, daca ar fi 2 siruri identice printre aceste k rotatii, sirul nu ar avea cum sa fie neperiodic. Dintre acestea k, 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, doar ca am ales exact una dintre ele prin compararea lexicografica, care nu poate rezulta in egalitate, intrucat sirul este neperiodic.

Dar toate acestea nu inseamna decat ca e suficient sa gasim numarul de siruri canonice, pe care apoi sa il inmultim cu numarul k, pentru a afla $\chi(k)$ . Putem pleca de la ideea ca orice sir care respecta conditiile din tabel este canonic, daca in plus respecta si conditia pe care am impus-o pentru k par (care nu face decat sa injumatateasca factorul de k, fapt pentru care vom da o demonstratie alternativa), cu exceptia acelor siruri care le respecta pe toate acesea, doar ca sunt periodice. 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 periodice si neperiodice de marime k care respecta relatiile din categoria $\Theta$ , daca eventual le-am supune unei rotatii, vedem ca:

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

Mica, dar folositoare, digresiune. O alta modalitate de a intelege de ce impartim la 2 in cazul in care k e par, e urmatoarea: In loc sa numim sir canonic doar unul din cele 2 posibile, le putem considera pe amandoua. Totul ramane neschimbat, doar ca acum fiecare sir canonic are o gama de $\frac{k}{2}$ de rotatii proprii, pentru ca le imparte pe cele k cu perechea sa. In aceasta perspectiva, lucrurile care vor urma s-ar putea sa fie mai clare, pentru ca ar ridica mai putine intrebari. Cu toate acestea, vom reveni si vom folosi denumirea de sir canonic asa cum am stabilit-o mai inainte.

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! Atunci cand $\frac{k}{d}$ este par, periodicitatea impune ca $P_0 = P_{\frac{K}{2}}$ , deci doar $\gamma(k)$ e influentata in acest caz, si trebuie sa scadem $\beta(d) + \gamma(d)$ , daca d e par, respectiv $\alpha(d)$ , daca d e impar. Atunci cand $\frac{k}{d}$ e impar: pe de o parte, d e par, iar pe de alta parte, 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} \psi(d)$ , unde $\psi(d)$ e o combinatie de $\chi'(d)$ , in functie de $\Theta$ si paritatea lui d. Daca analizam aceste cazuri, vedem ca se pot scrie mult mai usor, notand cu $\delta(k)$ numarul de siruri neperiodice de marime k pentru care una din rotatii face parte din cele 3 categorii:

$\delta(k) = \frac{k}{2^{(k + 1) - 2 [\frac{k + 1}{2}]}} \Sigma^{[\frac{k + 2}{2}]} - \sum_{d = 1, d | k}^{k - 1} \delta(d)$

Pe cat de compact si promitator arata, sa nu uitam de unde am plecat. Noi trebuie sa stim, deoarece valoarea lui A difera in functie de categorii, cate din cele $\delta(k)$ siruri, pentru k par, fac parte din $\beta(k)$ si cate din $\gamma(k)$ . Din fericire, mai avem o supriza, daca ne uitam mai atent la metoda de calcul a primului numar: daca l e puterea (nu exponentul) maxima a lui 2 care il divide pe k, atunci $\beta(k) = \frac{k}{2} \Sigma^{\frac{k}{2}} (\Sigma - 1) - \beta(l)$ , unde termenul al doilea este folosit doar daca l < k, adica daca k nu e el insusi putere de 2. Dar $\beta(l)$ este putere de 2, deci atunci cand k nu este putere de 2, $\beta(k) = (\Sigma - 1)(\frac{k}{2} \Sigma^{\frac{k}{2}} - \frac{l}{2} \Sigma^{\frac{l}{2}})$ .

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 64 (ar fi un lowerbound pentru orice idee decenta) si 100 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 n, 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

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.

infoarena informatica de performanta

Solutia problemei NrChei