h3. ( problema medie )

In primul rand observam ca nu are sens sa actionam un comutator de 2 sau mai multe ori. Plecam de pe linia $N$, coloana $N$ a panoului $A$. Daca $A[N][N] != B[N][N]$ este clar ca trebuie sa actionam comutatorul situat pe aceasta pozitie. Apoi ne uitam la pozitiile $(N, N-1)$ $(N, N-2)$ .. $(N, 1)$ in ordinea aceasta si procedam similar (unele comutari vor fi fortate). Apoi ne uitam la pozitiile $(N-1, N)$ $(N-2, N)$ .. $(1, N)$ si iarasi unele dintre aceste pozitii vor trebui comutate neaparat. Continuam acest algoritm pentru fiecare pozitie $(i, i)$ din panoul $A$, variabila $i$ fiind parcursa descrescator. O implementare directa a algoritmului are complexitate $O(N^3^)$, pentru a reduce complexitatea la $O(N^2^)$ observam ca la un moment dat, noi trebuie sa stim in ce stare se afla becul situat pe o pozitie $(i, j)$. Starea in care se afla acest bec este $(A[i][j]+L[i]+C[j])%2$, unde $A[i][j]$ reprezinta starea initiala a becului, $L[i]$ numarul de comutari efectuate pe linia $i$ pana in prezent, iar $C[j]$ numarul de comutari efectuate pe coloana $j$ pana in prezent. Cum am efectuat doar acele comutari care trebuiau neaparat efectuate acesta este si numarul minim de comutari necesare.

In primul rand observam ca nu are sens sa actionam un comutator de 2 sau mai multe ori. Plecam de pe linia $N$, coloana $N$ a panoului $A$. Daca $A[N][N]!=B[N][N]$ este clar ca trebuie sa actionam comutatorul situat pe aceasta pozitie. Apoi ne uitam la pozitiile $(N, N-1)$ $(N, N-2)$ .. $(N, 1)$ in ordinea aceasta si procedam similar (unele comutari vor fi fortate). Apoi ne uitam la pozitiile $(N-1, N)$ $(N-2, N)$ .. $(1, N)$ si iarasi unele dintre aceste pozitii vor trebui comutate neaparat. Continuam acest algoritm pentru fiecare pozitie $(i, i)$ din panoul $A$, variabila $i$ fiind parcursa descrescator. O implementare directa a algoritmului are complexitate $O(N^3^)$, pentru a reduce complexitatea la $O(N^2^)$ observam ca la un moment dat, noi trebuie sa stim in ce stare se afla becul situat pe o pozitie $(i, j)$. Starea in care se afla acest bec este $(A[i][j]+L[i]+C[j])%2$, unde $A[i][j]$ reprezinta starea initiala a becului, $L[i]$ numarul de comutari efectuate pe linia $i$ pana in prezent, iar $C[j]$ numarul de comutari efectuate pe coloana $j$ pana in prezent. Cum am efectuat doar acele comutari care trebuiau neaparat efectuate acesta este si numarul minim de comutari necesare.

h2. 'Ordini':problema/ordini