** 'Problema 1':elimirare-gaussiana#problema-1
** 'Go2':eliminare-gaussiana#go2
** 'Gxor':eliminare-gaussiana#gxor

** 'XMAX':eliminare-gaussiana#xmax

* 'Bibliografie':eliminare-gaussiana#bibliografie
h2(#descriere). Descriere

Î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)
 
Se dă o mulţime de $N (N<100 000)$ numere. Trebuie să aflăm submulţimea a cărei sumă xor este maximă.
 
h3. Soluţie
 
Să presupunem că avem un număr şi dorim să aflăm dacă poate fi obţinut. Pentru asta vom construi un sistem în care fiecare ecuaţie  corespunde unui bit, iar fiecare necunoscută corespunde unui număr dintre cele date. Dacă numărul are acel bit egal cu $1$ atunci în ecuaţie va apărea pe poziţia numărului un $1$(practic necunoscuta ne spune dacă considerăm acel număr în soluţie sau nu). Pentru fiecare bit din număr ecuaţia corespunzătoare va fi egală cu valoarea lui. Dacă sistemul are soluţie atunci există o submulţime a cărui xor să fie egal cu acel număr.
 
Acum ne rămâne să găsim numărul maxim pentru care sistemul are soluţie. Prima dată vom vedea dacă cel mai semnificativ bit poate fi egal cu $1$. Pentru asta vom avea un sistem cu o singură ecuaţie corespunzătoare primului bit. Dacă are soluţie vom păstra ecuaţia şi vom încerca să setăm şi al doilea bit cu $1$. În mod evident rezultatul va avea primul bit $1$. Dacă nu, atunci vom păstra ecuaţia dar o vom egala cu $0$. Pentru a afla soluţia vom adăuga pe rând câte o ecuaţie la sistem care iniţial va fi egală cu $1$ iar dacă sistemul nu are soluţie o vom egala cu $0$.
 
==code(cpp) |
//v - şirul de numere
//DB numărul maxim de biţi din care poate fi format un număr
//ss - matricea extinsă
//sz - numărul de ecuaţii din sistem
for(int b=DB-1; b>=0; --b) for(int i=0; i<n; ++i) if(v[i]&(1LL<<b)) ss[DB-b-1][i]=1;
for(int b=DB-1; b>=0; --b) {
  ++sz;
  ss[sz-1][n]=1;
  if(areSolutie()) rez|=(1LL<<b);
  else ss[sz-1][n]=0;
}
==
 
'XorCards':http://community.topcoder.com/stat?c=problem_statement&pm=12079&rd=15702&rm=318625&cr=22895893

'The magic matrix':http://community.topcoder.com/stat?c=problem_statement&pm=12495
https://apps.topcoder.com/wiki/display/tc/TCO+2013+Round+2A#TheMagicMatrix
'Minesweeper':http://www.infoarena.ro/problema/minesweeper