h2. poly

Problema este una de programare dinamica si are complexitatea $O(N)$, de constanta $2^7^ = 128$. Sa notam cu $M{~i,j~}$ lungimea celui mai lung subsir utilizand primele $i$ numere din vector astfel incat ultimul element din subsirul optim sa aiba ca divizori numerele din multimea data corespunzatoare bitilor de $1$ din $j$. Mai intai $M{~i,j~}$ = $M{~i-1,j~}$ ( nu folosim numarul al $i$-lea ). Daca dorim sa folosim si numarul al $i$-lea, atunci $M{~i,config~} = maxim(M{~i,config~}$, $M{~i-1,k~} + 1)$, cu $k and config = 0$, unde config are bitii de $1$ corespunzatori numerelor din multimea data cu care se divide acest al $i$-lea numar din sirul initial. Conditia $k and config$ ne asigura ca penultimul si ultimul numar din subsir nu au amandoua vreun divizor comun din multimea data (operatia $and$ in acest context este o operatie pe biti). Rezultatul va fi $max(M{~n,0~}$, $M{~n,1~}$... $M{~n,127~})$. Memoria folosita poate fi $O(1)$, retinand doar ultimele doua linii ale matricei.

Problema este una de programare dinamica si are complexitatea $O(N)$, de constanta $2^7^ = 128$. Sa notam cu $M{~i,j~}$ lungimea celui mai lung subsir utilizand primele $i$ numere din vector astfel incat ultimul element din subsirul optim sa aiba ca divizori numerele din multimea data corespunzatoare bitilor de $1$ din $j$. Mai intai $M{~i,j~}$ = $M{~i-1,j~}$ ( nu folosim numarul al $i$-lea ). Daca dorim sa folosim si numarul al $i$-lea, atunci $M{~i,config~} = maxim(M{~i,config~}$, $M{~i-1,k~} + 1)$, cu $k and config = 0$, unde $config$ are bitii de $1$ corespunzatori numerelor din multimea data cu care se divide acest al $i$-lea numar din sirul initial. Conditia $k and config$ ne asigura ca penultimul si ultimul numar din subsir nu au amandoua vreun divizor comun din multimea data (operatia $and$ in acest context este o operatie pe biti). Rezultatul va fi $max(M{~n,0~}$, $M{~n,1~}$... $M{~n,127~})$. Memoria folosita poate fi $O(1)$, retinand doar ultimele doua linii ale matricei.

Un algoritm de complexitate patratica in $N$ folosind tot programarea dinamica ar fi obtinut $30-40$ de puncte.