Swaps2

Solutie O(N)
Pentru ca un sir de biti sa fie sortat trebuie ca fiecare bit cu valoarea 0 sa fie inaintea fiecarui bit cu
valoarea 1. De aceea, daca facem un swap, este optim sa interschimbam cel mai din dreapta 0 cu cel mai din stanga 1. Pentru a sorta sirul vom aplica o strategie greedy, si anume: folosim doi indici st si dr cu care pornim din cele doua extremitati ale sirului (stanga si dreapta). st va merge spre dreapta iar dr spre stanga. Deplasam indicii pana cand gasim o pereche (st, dr) pentru care bitii trebuie interschimbati. Repetam procesul cat timp st < dr si retinem fiecare interschimbare ce trebuie facuta.

Fragment de cod:

vector<pair<int, int> > swaps;

st = 0;
dr = N - 1;
	
while(st < dr) {
	while(st < dr && sir[st] == '0') st++;
	while(st < dr && sir[dr] == '1') dr--;
	if(st < dr) {
		swaps.push_back(make_pair(st, dr));
		st++;
		dr--;
	}
}

Distincte2

Solutie O(N + M)
Deoarece avem de raspuns la M intrebari iar M poate fi destul de mare, trebuie sa precalculam niste valori pentru ca sa putem raspunde la fiecare cat mai eficient. Vom calcula un tablou C, avand semnificatia C[i] = numarul de vraji distincte ce au codurile in intervalul [1, i]. Avand aceste informatii, pentru o pereche (X, Y) raspunsul va fi C[X] - C[Y - 1].

Fragment de cod:

// avem codurile vrajilor in tabloul A
// precalculam tabloul C
for(i = 0; i < N; i++)
	B[A[i]] = 1;
	
C[0] = 0;
for(i = 1; i < MAXV; i++)
	C[i] = C[i - 1] + B[i];

// afisarea solutiei este banala

Solutie O(NlogN + MlogN)
Este posibila si o alta solutie. Retinem tabloul cu codurile vrajilor astfel incat ele sa fie in ordine crescatoare si fiecare sa apara o singura data. Putem face doua cautari binare: una ca sa gasim indicele st care este primul indice in tabloul sortat la care codul vrajii este mai mare sau egal decat X si inca una ca sa gasim indicele dr care este ultimul indice in acelasi tablou la care codul vrajii este mai mic sau egal decat Y. Raspunsul in acest caz va fi dr - st + 1.

Shift

Solutie O(N)
Primul pas este citirea datelor si memorarea lor intr-o forma convenabila. Ne folosim de faptul ca fiecare litera apare de exact 2 ori pe banda. Calculam doua tablouri, poz si cost, cu semnificatia poz[i][j] = pozitia de pe banda pe care apare litera a i-a din alfabet(incepe de la 0) a j-a oara, cost[i][j] = costul pentru a citi litera care se afla pe pozitia poz[i][j] pe banda. Raspunsul il calculam folosind programare dinamica. Observam ca pentru o anumita litera nu ne intereseaza decat la a cata aparitie a ei deplasam capul de citire si unde a ramas acesta la citirea anterioara. Reprezentam o stare printr-o pereche (i, j), unde i este pozitia la care am ajuns in S si j numarul aparitiei pentru litera S[i]. Daca notam idx = S[i] - 'a' si pidx = S[i - 1] - 'a', relatia de recurenta este tmin(i, j) = cost[idx][j] + min( tmin(i - 1, k) + abs(poz[idx][j] - poz[pidx][k]) ) pentru orice 1 <= j,k <= 2 (minimul se calculeaza pentru cele doua valori ale lui k; abs(x) este modulul lui x). Cazul de baza este la prima litera(initial capul de citire se afla pe pozitia 0): tmin(0, j) = cost[idx][j] + poz[idx][j]. Raspunsul final este min( tmin(N - 1, 1), tmin(N - 1, 2) ).

Fragment de cod:

idx = S[0] - 'a';
tmin[0][1] = cost[idx][1] + poz[idx][1];
tmin[0][2] = cost[idx][2] + poz[idx][2];

for(i = 1; i < n; i++) {
	pidx = idx;
	idx = S[i] - 'a';
        
	// vin la prima aparitie a literei S[i]
	d1 = abs(poz[idx][1] - poz[pidx][1]);
	d2 = abs(poz[idx][1] - poz[pidx][2]);
	tmin[i][1] = cost[idx][1] + min(tmin[i - 1][1] + d1, tmin[i - 1][2] + d2);
	
	// vin la a doua aparitie a literei S[i]
	d1 = abs(poz[idx][2] - poz[pidx][1]);
	d2 = abs(poz[idx][2] - poz[pidx][2]);
	tmin[i][2] = cost[idx][2] + min(tmin[i - 1][1] + d1, tmin[i - 1][2] + d2);
}

Ternar

Solutie O(N*M)
Din moment ce dreptunghiul trebuie sa contina doar 2 in interior, cautam toate zonele de 2 care sunt inconjurate de alte valori. Acest lucru il facem printr-un algoritm de fill. Pentru fiecare zona retinem valorile min_i, min_j, max_i, max_j, care reprezinta randul minim care contine o valoare de 2 din aceasta zona, asemanatoare si celelalte trei. Pentru ca aceasta zona sa fie una valida, trebuie ca dreptunghiul cu varful stanga-sus (min_i, min_j) si varful dreapta-jos (max_i, max_j) sa contina doar valori de 2. In plus, trebuie ca acest dreptunghi sa fie inconjurat doar de valori de 1. Aceasta verificare se poate face pargurgand efectiv potentialul dreptunghi sau prin alte metode mai inteligente. In caz ca zona e valida, avem un dreptunghi de arie (max_i - min_i + 3) * (max_j - min_j + 3) si verificam daca nu e solutie mai buna decat cea curenta. Mai avem de verificat dreptunghiurile speciale care au una dintre laturi de lungime 1 sau 2, dupa care avem raspunsul final.