* daca $C=0$ atunci $cnt0(i, j) = cnt0(i-1, j) + 9 * cnt(i-1, j)$
* altfel $cnt0(i, j) = cnt0(i-1, j) + 8 * cnt(i-1, j) + cnt(i-1, j-1)$

Cele doua matrici au marimi $lgB*K$ deci construirea lor va avea complexitate {$O(lg B*K)$}. Odata disponibile aceste informatii se poate realiza destul de usor functia {$f(x)$}. Nu voi prezenta aici toate detaliile deoarecere apar mai multe cazuri (in special cand {$C = 0$}), lasand ca exercitiu pentru cititor.

Cele doua matrice au marimi $lgB*K$ deci construirea lor va avea complexitate {$O(lg B*K)$}. Odata disponibile aceste informatii se poate realiza destul de usor functia {$f(x)$}. Nu voi prezenta aici toate detaliile deoarecere apar mai multe cazuri (in special cand {$C = 0$}), lasand ca exercitiu pentru cititor.

O alta rezolvare posibila ar fi calcularea functiei $f(x)$ in $O(2^lg10(x)^*lg10(x))$ astfel: pe fiecare pozitie intre $0$ si $lg10(x)$ avem doua variante, fie punem cifra {$C$}, fie alta cifra. Pentru fiecare astfel de configuratie cu cel putin $K$ cifre de $C$ se poate determina dintr-o parcurgere cate numere exista $< x$ care au cifre de $C$ in pozitiile respective.

* {$A{~i,j~} = max(A{~i,j-1~}, A{~i-1,k~} + S{~j~} - S{~k~})$}, pentru fiecare $k<j$

Al doilea termen este de forma $A{~i-1,k~} - S{~k~}$ (termen independent de {$j$}) + {$S{~j~}$}. Astfel din linia $i-1$ a matricii de dinamica pentru fiecare $j$ ne trebuie valoarea maxima $A{~i-1,k~}-S{~k~}$ cu {$k<j$}. O prima idee ar fi ca pe masura ce construim linia i sa inseram elementele din linia $i-1$ intr-un max-heap astfel reducand complexitatea la {$O(N*lgN*K)$}.

Al doilea termen este de forma $A{~i-1,k~} - S{~k~}$ (termen independent de {$j$}) + {$S{~j~}$}. Astfel din linia $i-1$ a matricei de dinamica pentru fiecare $j$ ne trebuie valoarea maxima $A{~i-1,k~}-S{~k~}$ cu {$k<j$}. O prima idee ar fi ca pe masura ce construim linia i sa inseram elementele din linia $i-1$ intr-un max-heap astfel reducand complexitatea la {$O(N*lgN*K)$}.

Cei care au rezolvat probleme precum "secventa":problema/secventa de pe infoarena, "trans":problema/trans de la barajul de la ONI 2004 sau divide de la USACO Ianuarie 2005 vor realiza imediat ca putem reduce complexitatea la $O(N*K)$ folosind structura necesara in rezolvarea acelor probleme si anume o coada (in literatura de specialitate se intalneste ca "deque with heap order"). Aceasta structura a mai fost tratata si in solutiilor problemelor prezentate mai sus, deci nu voi intra in detalii. Este evident ca un algoritm de complexitate $O(N*K)$ se incadreaza in timp, dar mai apare in calcul faptul ca sirul este circular. Un algoritm $O(N*K)$ care nu trateaza acest lucru ia $40$ de puncte. O prima idee ar fi sa aplicam acelasi algoritm pe fiecare permutare circulara dar se ridica complexitatea iar la {$O(N^2^*K)$}. Aceasta abordare ar trebui sa obtina intre $50$ si $60$ de puncte. Putem trata circularitatea sirului tot in $O(N*K)$ incercand sa obtinem o secventa care contine elemente $N$ si {$1$}. Putem realiza acest lucru astfel: