</tex>

h3. Soluţie
 

Această problemă este destul de des întâlnită la concursurile de programare şi pune unele dificultăţi deoarece toate variabilele depind între ele, problema neputând fi împărţită în subprobleme. Pentru a rezolva problema vom asocia sistemului o matrice în care pentru fiecare ecuaţie vom pune pe linia ei şi coloana corespunzătoare variabilelor care apar în ecuaţie valoarea $1$, iar pe ultima coloană vom pune rezultatul ecuaţiei. Matricea obţinută vom încerca să o reducem. Pentru a o reduce vom folosi două operaţii:
<tex>L_{i} \longleftrightarrow L_{j}</tex> : interschimbarea a două linii
<tex>L_{j} \longleftarrow L_{j} \oplus L_{i}</tex> unde <tex>L_{i}</tex> este o linie a matricei.

În mod evident o primă soluţie ar fi să considerăm fiecare celulă o necunoscută şi pentru fiecare informaţie să introducem o ecuaţie în sistem. Astfel vom avea $N*N$ necunoscute, ceea ce este prea mult pentru a intra în timp. În continuare vom lucra cu matricea $M[i][j]$ = suma xor a elementelor care se află în submatricea $(1,1)$ $(i,j)$, astfel pentru o informaţie x1, y1, x2, y2, r vom şti că $M[x2][y2] xor M[x1-1][y2] xor M[x2][y1-1] xor M[x1-1][y1-1] = r$. Vom aplica eliminarea gaussiană pe această matrice. Numărul de soluţii va fi <tex>2^{N*N-P}</tex>, unde $P$ e numărul de variabile fixe din sistem.

h2(#xmax). 'XMAX':http://www.spoj.com/problems/XMAX/ (Spoj,sgu)

h2(#xmax). XMAX ('Spoj':http://www.spoj.com/problems/XMAX/, 'sgu':http://acm.sgu.ru/problem.php?contest=0&problem=275)

Se dă o mulţime de $N (N<100 000)$ numere. Trebuie să aflăm submulţimea a cărei sumă xor este maximă.

https://apps.topcoder.com/wiki/display/tc/TCO+2013+Round+2A#TheMagicMatrix
'Minesweeper':http://www.infoarena.ro/problema/minesweeper
'Cracking RSA':http://acm.sgu.ru/problem.php?contest=0&problem=200

'Find the operations':https://www.hackerrank.com/contests/nov13/challenges/FLIP

h2(#bibliografie). Bibliografie