Pentru $k$ par, povestea se repeta! *Perioada pastreaza categoria sirului mare*, asa ca e suficient sa scadem <tex> \chi(d) </tex> din <tex> \chi(k) </tex>. In general, observam ca:
<tex> \chi(k) = \Upsilon_{\Theta}(k) - \sum_{d = 1, d | k}^{k - 1} \chi(d) </tex>
$(*): $ <tex> \chi(k) = \Upsilon_{\Theta}(k) - \sum_{d = 1, d | k}^{k - 1} \chi(d) </tex>
Pentru a calcula numarul de siruri din ultima categorie, de fapt vom calcula in <tex> \chi(k) </tex> numarul total de siruri neperiodice, iar la final vom scadea cate fac parte din celelalte categorii, si anume: <tex> k \alpha(k) </tex> (daca $k$ e impar) sau <tex> \frac{k}{2} (\beta(k) + \gamma(\frac{k}{2})) </tex> (daca $k$ e par)
Pentru a calcula numarul de siruri din ultima categorie, *de fapt* vom calcula in <tex> \chi(k) </tex> numarul total de siruri neperiodice, iar la final vom scadea cate fac parte din celelalte categorii, si anume: <tex> k \alpha(k) </tex> (daca $k$ e impar) sau <tex> \frac{k}{2} (\beta(k) + \gamma(k)) </tex> (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 <tex> \delta(k) </tex> 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:
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 <tex> \delta(k) </tex> 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 <tex> \Sigma^{h} </tex>, atunci cand sunt cerute, in <tex> O(h) </tex>. _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 <tex> \Sigma </tex>, il putem cauta pe $T$ in <tex> O(log(n)) </tex> sau in <tex> O(1) </tex>, 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
* 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.
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 <tex> \chi(k) </tex> fara sa fie nevoie sa calculam valorile <tex> \chi(d) </tex>. Sa analizam, mai exact, care este factorul, notat cu $f()$, cu care trebuie adunat <tex> \Upsilon_{\Theta}(d) </tex> la raspuns, pentru fiecare $d$. De exemplu, daca $k = 2 * 3 * 5$ sa zicem, putem vedea ca <tex> f(\Upsilon_{\Theta}(2 * 3 * 5)) = 1 </tex>, <tex> f(\Upsilon_{\Theta}(2 * 3)) = f(\Upsilon_{\Theta}(2 * 5)) = f(\Upsilon_{\Theta}(3 * 5)) = -1 </tex>, <tex> f(\Upsilon_{\Theta}(2)) = f(\Upsilon_{\Theta}(3)) = f(\Upsilon_{\Theta}(5)) = 1 </tex>, respectiv <tex> f(\Upsilon_{\Theta}(1)) = -1 </tex>. Acest fenomen se generalizeaza in felul urmator:
* Fie $k = p{~0~}^a{~0~}^ * p{~1~}^a{~1~}^ * ... * p{~r-1~}^a{~r-1~}^$, descompunerea in factori primi a lui $k$
* <tex> 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} </tex>, orice $d$ pentru care, oricare ar fi $i$, fie $b{~i~} = a{~i~}$, fie $b{~i~} = a{~i~} - 1$
* <tex> f(\Upsilon_{\Theta}(d = p_0^{b_0} p_1^{b_1} \ldots p_{r-1}^{b_{r-1}})) = 0 </tex>, 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 <tex> \chi(k) </tex>, 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^i^ `and` mask)$ si vom aduna la rapuns <tex> (-1)^{popcount(mask)} \Upsilon_{\Theta}(d) </tex>. 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.
