Clasa a 9 -a :
And
Pentru o secvenţă a(i), a(i+1), ..., a(j), valoarea a(i) and a(i+1) and ... and a(j) este nenulă dacă există măcar un bit din reprezentarea tuturor numerelor din secvenţă în baza 2 care este setat cu 1. Considerând că valoarea maximă din şir este MAX care se reprezintă pe maximum k biţi (numerotaţi de la 0 la k-1), atunci o soluţie a problemei este să luăm fiecare bit b=0..k-1 şi să determinăm care este lungimea maximă a unei secvenţe care are bitul b egal cu 1.
Pentru a verifica dacă un număr natural x are bitul 1 setat pe poziţia b există mai multe metode, una din ele fiind verificarea dacă expresia x & (1 << b) este nenulă, unde prin << s-a notat operatorul de shiftare la stânga (care în Pascal se notează cu shl).
Complexitatea algoritmului este O(n x log(MAX))
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
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.
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ă.
Complexitate finală O(N x N + Q log N)
Permuta
Aceasta este o problemă foarte simplă, este suficient să refacem în mod invers operaţiile descrise în enunţ. Complexitate O(N).
Clasa a 10-a:
Vis
Considerăm S punctul de coordonate (1,1), F ca fiind punctul de coordonate (N,N), A este punctul (L1,C1), iar B este punctul (L2,C2).
Cu un algoritm de parcurgere în lăţime se calculează:
- distanţa de la S la F mergând doar pe valori de 0
- distanţa de la S la A mergând doar pe 0, apoi distanţa de la A la F mergând pe valori <= K1
- distanţa de la S la B mergând doar pe 0, apoi distanţa de la B la F mergând pe valori de 0 sau >= K2
- distanţa de la S la A mergând doar pe 0, apoi distanţa de la A la B mergând pe valori <= K1, apoi distanţa de la B la F mergând pe valori <= K1 sau >= K2.
- distanţa de la S la B mergând doar pe 0, apoi distanţa de la B la A mergând pe valori de zero sau >= K2, apoi distanţa de la B la F mergând pe valori <= K1 sau >= K2.
Această abordare era suficientă pentru a obţine 100 de puncte
Strabunica
Pentru fiecare valoare a(i) din şir se construiesc valorile:
st(i)=numărul valorilor din şir aflate la stânga poziţiei i şi care sunt mai mari sau egale cu a(i)
dr(i)=numărul valorilor din şir aflate la dreapta poziţiei i şi care sunt mai mari sau egale cu a(i)
Cei doi vectori se pot construi liniar utilizând o stivă.
Se parcurge apoi şirul şi se determină valoarea max{a(i)*(st(i)+dr(i)+1)}, i=1..N
Atenţie la faptul că rezultatul este long long.
Complexitate O(N)
Maxk
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, 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
b. Dacă prin eliminarea subsecvenţei a(i..j) există valori care au fr(i) > K, atunci avansăm cu j.
Clasele 11-12:
Qxy
Carry
Problema se rezolvă prin programare dinamică. Se construieşte matricea tridimensională bst, în care bst(i,j,t) = numărul de numere de i cifre care adunate cu x dau de j ori transport 1, având dupa cele i adunări transportul t, unde t=0..1
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))
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 ];
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).
