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 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 este valida 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 (t1 - t2, t1+1 - t2, t2+2 - t2, etc). 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 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)

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

Observam usor ca numerele cautate sunt puteri de numere prime mai mici decat 10 la puterea a 6-a (de aici restrictia ca puterea sa fie cel putin 2). Vom folosi ciurul lui Eratostene pentru a determina aceste numere prime de la 2 la 1.000.000 . Pentru fiecare numar prim, vom calcula puterile sale cu valoare mai mica decat B (observam ca vom avea putine numere intrucat, cu cat creste valoarea numarului prim, cu atat scade puterea sa astfel incat sa fie mai mica decat B ). Dupa ce am introdus toate aceste puteri intr-un vector, il vom sorta. Pentru a raspunde la query-uri, observam ca numarul elementelor valide mai mici sau egale decat B minus numarul elementelor valide mai mici decat A ne ofera numarul elementelor valide intre A si B; vom folosi cautare binara pentru aceste 2 pozitii in vectorul creat anterior, iar raspunsul va fi dat de diferenta dintre cele 2 pozitii.

Observam usor ca numerele cautate sunt puteri de numere prime mai mici decat 10 la puterea a 6-a (de aici restrictia ca puterea sa fie cel putin 2). Vom folosi ciurul lui Eratostene pentru a determina aceste numere prime. Pentru fiecare numar prim, vom calcula puterile sale cu valoare mai mica decat B (observam ca vom avea putine numere intrucat, cu cat creste valoarea numarului prim, cu atat scade puterea sa astfel incat sa fie mai mica decat B ). Dupa ce am introdus toate aceste puteri intr-un vector, il vom sorta. Pentru a raspunde la query-uri, observam ca numarul elementelor valide mai mici sau egale decat B minus numarul elementelor valide mai mici decat A ne ofera numarul elementelor valide intre A si B; vom folosi cautare binara pentru aceste 2 pozitii in vectorul creat anterior, iar raspunsul va fi dat de diferenta dintre cele 2 pozitii.

h2. "Logik":https://infoarena.ro/problema/logik
Problema ne cere sa verificam pentru fiecare bit i daca exista o valoare a unei subsecvente valide care are 0 in bitul i, astfel facand operatia AND rezultatul va avea 0 pe bitul i.

Prima observatie care trebuie facuta este ca dupa ce faci AND cu valoarea unei subsecvente valide, nu mai este necesar sa faci AND cu alte subsecvente valide care o includ pe aceasta, deoarece nu se va schimba rezultatul.

Prima observatie care trebuie facuta este ca, dupa ce faci AND cu valoarea unei subsecvente valide, nu mai este necesar sa faci AND cu alte subsecvente valide care o includ pe aceasta, deoarece nu se va schimba rezultatul.

Acest lucru se datoreaza faptului ca operatia OR nu schimba bitii de 1, eventual schimba biti de 0 in 1.
Acum, facand AND-ul tuturor numerelor pare (subsecventele de un element par sunt valide) va mai trebui sa verificam subsecventele valide care contin doar numere impare.
Cum toate subsecventele valide de numere impare contin cel putin o subsecventa valida de 2 numere impare, este de ajuns sa mai facem AND cu valoarea tuturor subsecventelor de 2 numere impare (2 numere impare consecutive).

h2. "Rusuoaica":https://infoarena.ro/problema/rusuoaica

In primul rand, putem sa vindem muchiile cu cost mai mare ca A pentru ca nu le vom folosi niciodata; daca vom avea nevoie de ele le putem cumpara cu cost fix A. Vom avea nevoie acum pentru fiecare componenta conexa formata cu muchiile ramase, de APM-ul sau. Dupa ce determinam APM-ul pentru fiecare componenta, la raspuns se va adauga (nr_comp_conexe - 1) * A pentru a le uni intr-un singur arbore. Putem implementa usor folosind paduri de multimi disjuncte si incercand muchiile pe rand in ordine sortata in functie de cost. Daca muchia va lega 2 componente conexe la un moment dat, o vom cumpara, altfel o vom vinde. La final putem determina cate muchii sa cumparam cu cost A, numarand cate radacini distincte avem in padurea de multimi disjuncte sau facand componentele conexe cu DFS pe un nou graf doar cu muchiile pastrate.

In primul rand, putem sa vindem muchiile cu cost mai mare ca A pentru ca nu le vom folosi niciodata; daca vom avea nevoie de ele le putem cumpara cu cost fix A. Vom avea nevoie acum pentru fiecare componenta conexa formata cu muchiile ramase, de APM-ul sau. Dupa ce determinam APM-ul pentru fiecare componenta, la raspuns se va adauga (nr_comp_conexe - 1) * A pentru a le uni intr-un singur arbore. Putem implementa usor folosind paduri de multimi disjuncte si incercand muchiile pe rand in ordine sortata in functie de cost. Daca muchia va lega 2 componente conexe la un moment dat, o vom cumpara, altfel o vom vinde. La final putem determina cate muchii sa cumparam cu cost A, numarand cate radacini distincte avem in padurea de multimi disjuncte.

h2. "Vampir":https://infoarena.ro/problema/vampir

Daca L/2 este impar, nu va avea divizori pari, deci raspunsul va fi -1 pentru ambele cerinte.
De exemplu, pentru un K divizor par al lui L/2, un posibil drum este (0,0) -> (1*(K/2),1*(K/2)) -> (2*(K/2),2*(K/2)) -> .. -> ((L/2K)*(K/2),(L/2K)*(K/2)).
Pentru cerina 2 trebuie sa gasim drumul de cost minim dintre toti K gasiti la cerinta 1. Pentru un K fixat costul drumului minim este (L/2K)*B(K/2,K/2), daca notam functia asta cu B' observam ca este strict descrescatoare de la 2 pana la L/2, deci minimul functiei va fi cand K este maxim, respectiv L/2.

Raspunsul pentru cerinta 2 este B(L/4,L/4). (Se poate observa usor ca minimul este cand K este maxim deoarece factorialul de la numitor creste foarte repede).

Raspunsul pentru cerinta 2 este B(L/4,L/4). (Se poate observa usor ca minimul se realizeaza cu K maxim deoarece factorialul de la numitor creste foarte repede).

h2. "Sunmihai":https://infoarena.ro/problema/sunmihai

Acesta problema se rezolva cu metoda programarii dinamice. Vom calcula dp[i][j] - costul minim pentru a avea pe ultima piesa din domino valoarea din dreapta j, trecand prin primele i domino-uri date. Vom folosi notatia: v1[i] - valoarea din stanga a celui de-al i-lea domino dat initial si v2[i] - valoarea din dreapta. Dp[ 1 ][v2[ 1 ]] este 0 pentru ca nu aplicam nicio operatie primului domino, iar dp[ 1 ][v1[ 1 ]] este maxim A (v1[i] poate fi egal cu v2[i]), pentru ca intoarcem domino-ul; restul tabloului de dinamica il vom initializa cu o valoare mare. Ajunsi la a i-a piesa putem sa abordam in urmatorul fel: vrem sa o pastram exact cum e, iar dp[i][v2[i]] va fi dp[i-1][v1[i]]; vrem sa o intoarcem, iar dp[i][v1[i]] va fi dp[i-1][v2[i]] + A (atentie cand v1[i]=v2[i]), o scoatem cu cost B, iar dp[i][j] va fi egal cu dp[i-1][j] sau adaugam o piesa cu cost C. Piesa de tip C are sens sa fie adaugata doar cand vrem sa pastram a i-a piesa si nu avem anterior o piesa de care sa o legam, adica dp[i-1][v1[i] / v2[i]] este valoarea aceea mare cu care am initializat tabloul. Putand insera o piesa cu orice valori v1 si v2, nu ne intereseaza care sunt acestea si vom insera piesa dupa o configuratie dp[i-1][j], nu conteaza cine este j (de la 1 la 100), cu dp valoarea minima. Dp[i][v2[i]] va fi dp[i-1][j] (minim) + C. Raspunsul se va afla in min(dp[n][v1[i]], dp[n][v2[i]]).

Acesta problema se rezolva cu metoda programarii dinamice. Vom calcula dp[i][j] - costul minim pentru a avea pe ultima piesa din domino valoarea din dreapta j, trecand prin primele i domino-uri date. Vom folosi notatia: v1[i] - valoarea din stanga a celui de-al i-lea domino dat initial si v2[i] - valoarea din dreapta. Dp[1][v2[1]] este 0 pentru ca nu aplicam nicio operatie primului domino, iar dp[1][v1[1]] este maxim A (v1[i] poate fi egal cu v2[i]), pentru ca intoarcem domino-ul; restul tabloului de dinamica il vom initializa cu o valoare mare. Ajunsi la a i-a piesa putem sa abordam in urmatorul fel: vrem sa o pastram exact cum e, iar dp[i][v2[i]] va fi dp[i-1][v1[i]]; vrem sa o intoarcem, iar dp[i][v1[i]] va fi dp[i-1][v2[i]] + A (atentie cand v1[i]=v2[i]), o scoatem cu cost B, iar dp[i][j] va fi egal cu dp[i-1][j] sau adaugam o piesa cu cost C. Piesa de tip C are sens sa fie adaugata doar cand vrem sa pastram a i-a piesa si nu avem anterior o piesa de care sa o legam, adica dp[i-1][v1[i] / v2[i]] este valoarea aceea mare cu care am initializat tabloul. Putand insera o piesa cu orice valori v1 si v2, nu ne intereseaza care sunt acestea si vom insera piesa dupa o configuratie dp[i-1][j], nu conteaza cine este j (de la 1 la 100), cu dp valoarea minima. Dp[i][v2[i]] va fi dp[i-1][j] (minim) + C. Raspunsul se va afla in min(dp[n][v1[i]], dp[n][v2[i]]).

h2. "Negot":https://infoarena.ro/problema/negot