h2. "Nane":https://infoarena.ro/problema/nane

Problema aceasta se rezolva folosind "sliding window". Ce presupune rezolvarea: vom tine doi pointeri st si dr. Vom determina la fiecare pas, cate secvente sunt valide si se termina cu pozitia dr. Daca secventa i - j cu i<j este valida, si secventa i+1 - j  datorita naturii operatiei OR. Va trebui sa aflam pentru fiecare pozitie t2, cea mai mica pozitie t1 pentru care secventa este valida; lungimea acestei secvente va fi t2-t1+1 si vom avea t2-t1+1 secvente valide practic. Revenind la st si dr; cand incrementam dr cu o unitate, suma OR de la st la dr va ramane la fel sau va creste, in consecinta va trebui sa incermentam si st pana cand suma OR de la st la dr va avea mai putin de K biti de 1. Putem face acest lucru optim folosind un vector de aparitii a bitilor. Cand incrementam dr, vom incrementa si in vectorul de aparitii fiecare bit de 1 al elementului de pe pozitia dr, iar cand vrem sa incrementam st, vom decrementa fiecare bit al elementului de pe pozitia st. Complexitate O(N*K)

Problema aceasta se rezolva folosind "sliding window". Ce presupune rezolvarea: vom tine doi pointeri st si dr. Vom deterina la fiecare pas, cate secvente sunt valide si se termina cu pozitia dr. Daca secventa i - j cu i<j este valida, si secventa i+1 - j  datorita naturii operatiei OR. Va trebui sa aflam pentru fiecare pozitie t2, cea mai mica pozitie t1 pentru care secventa este valida; lungimea acestei secvente va fi t2-t1+1 si vom avea t2-t1+1 secvente valide practic. Revenind la st si dr; cand incrementam dr cu o unitate, suma OR de la st la dr va ramane la fel sau va creste, in consecinta va trebui sa incermentam si st pana cand suma OR de la st la dr va avea mai putin de K biti de 1. Putem face acest lucru optim folosind un vector de aparitii a bitilor. Cand incrementam dr, vom incrementa si in vectorul de aparitii fiecare bit de 1 al elementului de pe pozitia dr, iar cand vrem sa incrementam st, vom decrementa fiecare bit al elementului de pe pozitia st. Complexitate O(N*K)

h2. "Asi":https://infoarena.ro/problema/asi