* 'Aplicaţii':eliminare-gaussiana#aplicatii
** '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.

Având matricea redusă, numărul de soluţii este dat de numărul de coloane, fie el $x$, pe care nu am putut găsi un $1$ cu care să reducem liniile de mai jos. Astfel celelalte variabile vor fi determinate în funcţie de variabila corespunzătoare acestei coloane, sistemul avand soluţie indiferent de valoarea variabilei. În final numărul de soluţii va fi <tex>2^x</tex>.  Sistemul nu are soluţie atunci când avem o linie de forma <tex>\begin{pmatrix} 0 & 0 & 0 & 0 & 0 & 1\end{pmatrix}</tex>

Având matricea redusă, numărul de soluţii este dat de numărul de coloane, fie el $x$, pe care nu am putut găsi un $1$ cu care să reducem liniile de mai jos. Astfel celelalte variabile vor fi determinate în funcţie de variabila corespunzătoare acestei coloane, sistemul avand soluţie indiferent de valoarea variabilei. În final numărul de soluţii va fi <tex>2^x</tex>

h2(#go2). 'Go2':problema/go2 (Algoritmiada 2012 runda 4)

Astfel înlocuind variabilele cu cele corespunzătoare de pe prima linie rămânem cu un sistem cu $M$ variabile şi $MxN$ ecuaţii. În final complexitatea va fi <tex>O((M+N)^2*M)</tex>

h2(#gxor). 'Gxor':http://campion.edu.ro/arhiva/index.php?page=problem&action=view&id=1374 (Campion 2011)
 
bq. Se consideră o matrice cu N(N<30 001) linii şi N coloane (numerotate de la 1 la N). Fiecare element al matricei poate lua valoarea 0 sau 1. Se cunosc informaţii despre G(G<401) submatrice ale matricii considerate. A i-a submatrice este definită de parametrii l1(i), c1(i), l2(i) şi c2(i) (1≤l1(i)≤l2(i)≤N ; 1≤c1(i)≤c2(i)≤N). Se ştie că xor-ul tuturor elementelor din submatricea i (elementele cuprinse între liniile l1(i) şi l2(i) inclusiv şi între coloanele c1(i) şi c2(i) inclusiv) este x(i) (evident, x(i) este 0 sau 1).
Fie NM numărul de matrice binare cu N linii şi N coloane pentru care toate informaţiile despre cele G submatrice sunt adevărate (există în total 2N∙N matrici binare cu N linii şi N coloane, dar informaţiile despre cele G submatrice nu sunt neapărat adevărate pentru toate aceste matrice). Determinaţi restul împărţirii lui NM la 34949.
 
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;
}
==
 
'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