==include(page="onis-2015/solutii-runda-1/bujor")==
Constatarea cheie aici este ca daca inmultim matricele $B$ si $P$ obtinem matricea $I$ cu semnificatia:  @I[i][j] = total expected winnings pentru Bujor in casino-ul i, in ziua j@.

Observam ca matricele $I$ care satisfac cerinta finala sunt matricele permutare, printe care se numara si matricea identitate $I$~n~. Deci matricea P poate fi inversa matricei B. Matricea B este garantat inversabila deoarece se garanteaza ca exista solutie la problema (Ecuatia matriceala @B*P = I@ cu _det(I)_ nenul are solutie doar daca _det(B)_ este si el nenul)

Observam ca matricele @I@ care satisfac cerinta finala sunt matricele permutare, printe care se numara si matricea identitate $I$~n~. Deci matricea P poate fi inversa matricei B. Matricea B este garantat inversabila deoarece se garanteaza ca exista solutie la problema (Ecuatia matriceala @B*P = I@ cu _det(I)_ nenul are solutie doar daca _det(B)_ este si el nenul)

Inversa matricei se poate calcula in <tex>O(N^3)</tex> cu o variatie a 'algoritmului lui Gauss':http://www.infoarena.ro/problema/gauss care se cheama eliminare Gauss-Jordan. Prin inmultiri de linii cu constante, si scadere de linii din alte linii, putem aduce matricea B la matricea $I$~n~. Atunci operatiile pe care le-am efectuat sunt echivalente cu inmultirea cu matricea B^-1^. Daca retinem aceste operatii si le aplicam pe matricea $I$~n~, vom obtine matricea B^-1^. Mai multe explicatii/informatii se gasesc si 'aici':http://en.wikipedia.org/wiki/Gaussian_elimination