h2. 'Switch':infoarena.ro/problema/switch

O primă idee care poate rezolva această problemă este cea de a descrie un graf cu $16$ noduri (fiecare matrice posibila) şi $4$ arce care ies din fiecare nod (transformarile posibile). Astfel, se poate face un DFS pe acest graf pentru a se afla daca exista conexitate intre matricele date in input. Dacă problema ar fi cerut şi numărul minim de operaţii necesare, soluţia ar fi fost dată de o parcurgere în lăţime.

O primă idee care poate rezolva această problemă este cea de a descrie un graf cu 16 noduri (fiecare matrice posibila) şi 4 arce care ies din fiecare nod (transformarile posibile). Astfel, se poate face un DFS pe acest graf pentru a se afla daca exista conexitate intre matricele date in input. Dacă problema ar fi cerut şi numărul minim de operaţii necesare, soluţia ar fi fost dată de o parcurgere în lăţime.

Însă această problemă are o soluţie mult mai scurtă, pe care mulţi concurenţi au intuit-o şi au implementat-o. Graful are de fapt doar două componente conexe. În prima se află matricele cu număr par de $1$, iar în cealaltă cele cu număr impar. Pentru a demonstra acest lucru, observaţi că o operaţie de negare nu schimbă niciodată paritatea numărului de $1$ (De ce?). Faptul că din orice matrice pară se poate ajunge in orice altă matrice pară este destul de evident, în special fiindcă multe dintre configuraţii sunt doar oglindiri/rotiri ale celorlalte.