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

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