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.

Avand precalculate valorile de mai sus pentru fiecare nod al arborelui in parte vom putea raspunde in timp $O(logN)$ pentru fiecare din cele $M$ intrebari. Fiecare subsecventa data $x{~i~}, x{~i+1~}... x{~j~}$ va putea fi compusa din reuniunea mai multor noduri din arborele de intervale. Acum parcurgem nodurile ce compun subsecventa data de la dreapta la stanga si vom gasi rapid valorile $maxim(y)$ si $minim(z)$. Presupunand ca am ajuns la nodul $Q$ valoarea $maxim(y)$ pana aici se calculeaza astfel:

* @MAX(Y) = maxim (y_max(Q) ; y_max_max(Q) - min(W) ; x_min_max(Q)+max(W) ; max(Q)+max(W)-min(W)@

* @MAX(Y) = maxim (y_max(Q) ; y_max_max(Q) - min(W) ; x_min_max(Q)+max(W) ; max(Q)+max(W)-min(W))@

Analog se calculeaza si $minim(z)$.