** '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

b_{2} \\
\vdots \\
b_{n}

\end{pmatrix}</tex>

\end{pmatrix}

Pentru a rezolva sistemul vom transforma toate elementele de sub diagonala principală a matricei extinse în $0$ pentru a putea scrie fiecare necunoscută doar în funcţie de necunoscutele cu indici mai mari.

</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.

h3. Soluţie

Î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 ('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ă.
 
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;
}
==

Î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.

'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

'Go2':http://www.infoarena.ro/problema/go2
'Gxor':http://campion.edu.ro/arhiva/index.php?page=problem&action=view&id=1374

'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