h2. Qmatrix
De remarcat în primul rând faptul că matricea A de dimensiuni N x N care se generează nu poate fi memorată. Dar nici nu este nevoie. În schimb, se construiesc două matrice L şi C având fiecare 10 linii şi N coloane, în care

L[ c ][i] = numărul valorilor de c (c=0..9) aflate pe linia i din matricea A
C[ c ][i] = numărul valorilor de c (c=0..9) aflate pe coloana i din matricea A

L[ c ][ i ] = numărul valorilor de c (c=0..9) aflate pe linia i din matricea A
C[ c ][ i ] = numărul valorilor de c (c=0..9) aflate pe coloana i din matricea A

Cele două matrice se construiesc chiar la generarea elementelor matricei A, pentru că dacă A(i,j)=c, atunci rezultă că la linia i se află cifra c şi la coloana j se află cifra c.

Pornind de la cele două matrice L şi C, se construiesc apoi în aceleaşi două matrice sumele parţiale, adică pentru fiecare c=0..9 şi i=1..N,  L[c][i] va memora numărul de valori egale cu c aflate pe primele i linii din matricea A. Similar, C[c][i] va memora numărul de valori egale cu c aflate pe primele i coloane din matricea A.

Pornind de la cele două matrice L şi C, se construiesc apoi în aceleaşi două matrice sumele parţiale, adică pentru fiecare c=0..9 şi i=1..N,  L[ c ][ i ] va memora numărul de valori egale cu c aflate pe primele i linii din matricea A. Similar, C[ c ][ i ] va memora numărul de valori egale cu c aflate pe primele i coloane din matricea A.

Pentru fiecare interogare se va răspunde apoi în timp logaritmic căutând binar linia sau coloana pe care se află o anumită cifră.

Se construieşte de la început un vector de frecvenţe, în sensul că
fr(i)=numărul de apariţii ale valorii i în şirul iniţial

Pentru aproximativ 80 de puncte (şi complexitate liniar-logaritmică) se poate căuta binar lungimea secvenţei, având fixată lungimea L, căutându-se dacă există o secvenţă de L elemente care eliminate dau fr(i) <= K, pentru orice i=1..100000.

Pentru aproximativ 80 de puncte (şi complexitate liniar-logaritmică) se poate căuta binar lungimea secvenţei, având fixată lungimea L, verificând dacă există o secvenţă de L elemente care eliminate dau fr(i) <= K, pentru orice i=1..100000.

Pentru 100 de puncte (şi complexitate O(N)) se parcurge şirul cu doi indici i şi j, i <= j, considerând că elementele având indicii între i şi j sunt eliminate. Apar două cazuri:
a. Dacă prin eliminarea subsecvenţei a(i..j) toate valorile au fr(i) <= K, atunci se actualizează lungimea minimă şi avansează i

Dacă X este o singură cifră (N=1), atunci evident că şi K=1, atunci răspunsul este chiar X. De exemplu, dacă X=3, atunci numerele care dau un transport 1 sunt 7,8 şi 9.
Pentru N>=2, recurenţele sunt:
i=2..n-1, j=1..k:

bst[i][j][0] = (bst[i-1][j][0] * (10 - a[i]) + bst[i-1][j][1] * (9 - a[i]))
bst[i][j][1] = (bst[i-1][j-1][0] * a[i] + bst[i-1][j-1][1] * (a[i] + 1))

bst[ i ][ j ][ 0 ] = (bst[ i-1 ][ j ][ 0 ] * (10 - a[ i ]) + bst[ i-1 ][ j ][ 1 ] * (9 - a[ i ]))
bst[ i ][ j ][ 1 ] = (bst[ i-1 ][ j-1 ][ 0 ] * a[ i ] + bst[ i-1 ][ j-1 ][ 1 ] * (a[ i ] + 1))

Acestea se justifică astfel:
Un număr de i cifre care a dat j transporturi 1 la adunare se obţine dintr-un număr de i-1 cifre care avea deja j transporturi de 1, fie avea j-1 transporturi de 1 şi acum (la pasul i) s-a obţinut un nou transport.
Date iniţiale (uşor de intuit):

bst[1][0][0] = 10 - a[1];
bst[1][1][1] = a[1];

bst[ 1 ][ 0 ][ 0 ] = 10 - a[ 1 ];
bst[ 1 ][ 1 ][ 1 ] = a[ 1 ];

Trebuie analizat separat cazul când cifra cea mai semnificativă a lui X este 9 sau mai mică decât 9, pentru că este posibil să se obţină un transport 1 suplimentar.
Complexitate O(N*K).

h2. Arbzyz

h2. Arbxyz