Problema urmatoare a fost pusa in 2000 intr-un concurs prin e-mail in [GInfo]. Solutia de
mai jos (O(n^3+valfin*n^2)) a fost de aproape 100 de ori mai rapida decat cea mai buna metoda
cunoscuta pana atunci, care era O(valfin*n^3). Dar trebuie folosite numere fractionare
cu precizie marita daca m>35 si n>35. Programul original a castigat cele mai multe puncte
(30 din 100) pentru problema asta si, dupa ce a fost verificat de editorii GInfo si dupa
ce au fost corectate niste bug-uri si a fost adaugata precizie multipla, el a rezolvat corect
si rapid toate testele. Daca vreti programul construit, se gaseste la https://lalescu.ro/liviu/rubik/
Pentru orice nelamuriri sau detalii, va rugam scrieti autorului
(vedeti https://lalescu.ro/liviu/ pentru adresa e-mail).

Enunt [GInfo]:

Problema era ca se da o matrice A cu dimensiuni m*n (m si n intre 1 si 100), cu intregi.
O secventa consta in adaugarea unei valori intregi intr-o casuta si aceleiasi valori in fiecare dintre 
cele 2, 3 sau 4 casute adiacente orizontal si vertical, dar nu diagonal. Se cere o succesiune 
de secvente care sa duca la o matrice care contine in fiecare casuta o aceeasi valoare, valfin, 
intre 0 si 1000.

Solutie:

Notam A matricea de intrare, cu dimensiuni m*n
Notam X matricea solutie, cu dimensiuni m*n, unde (x11) se adauga la a(11) si la vecinii: a(12), a(21),
, ..., x(mn) se adauga la a(mn) si la vecinii: a(m,n-1), a(m-1,n).
Notam valfin valoarea care se obtine peste tot in matrice, 0<=valfin<=1000

Fie m=4, n=3 (exemplu)

Matricea initiala este:

a11 a12 a13 a14
a21 a22 a23 a24
a31 a32 a33 a34

Dupa ce aplicam matricea X (solutie) la A, avem:

valfin	valfin	valfin	valfin
valfin	valfin	valfin	valfin
valfin	valfin	valfin	valfin

Unde:
Pt. pozitia 11: valfin=a(11)+x(11)+x(12)+x(21)
Pt. pozitia 12: valfin=a(12)+x(11)+x(12)+x(13)+x(22)
Pt. pozitia 13: valfin=a(13)+x(12)+x(13)+x(14)+x(23)
Pt. pozitia 14: valfin=a(14)+x(13)+x(14)+x(24)

Presupunem ca cunoastem x(11), x(12), ..., x(1n) (prima linie a solutiei X)

Rezulta:
Pt. pozitia 11: x(21)=valfin-a(11)-x(11)-x(12)
Pt. pozitia 12: x(22)=valfin-a(12)-x(11)-x(12)-x(13)
Pt. pozitia 13: x(23)=valfin-a(13)-x(12)-x(13)-x(14)
Pt. pozitia 14: x(24)=valfin-a(14)-x(13)-x(14)

Adica:
(x21) (valfin-a11) (-1 -1  0  0) (x11)
(x22)=(valfin-a12)+(-1 -1 -1  0)*(x12)
(x23) (valfin-a13) ( 0 -1 -1 -1) (x13)
(x24) (valfin-a14) ( 0  0 -1 -1) (x14)

(un vector coloana este egal cu suma dintre un vector coloana si o matrice 4*4 inmultita cu un vector coloana)

Deci am determinat si a doua linie a solutiei, daca cunoastem prima linie.

Analog,
(x31) (valfin-a21) (-1 -1  0  0) (x21) (-1  0  0  0) (x11)
(x32)=(valfin-a22)+(-1 -1 -1  0)*(x22)+( 0 -1  0  0)*(x12)
(x33) (valfin-a23) ( 0 -1 -1 -1) (x23) ( 0  0 -1  0) (x13)
(x34) (valfin-a24) ( 0  0 -1 -1) (x24) ( 0  0  0 -1) (x14)

Analog,
(x41) (valfin-a31) (-1 -1  0  0) (x31) (-1  0  0  0) (x21)
(x42)=(valfin-a32)+(-1 -1 -1  0)*(x32)+( 0 -1  0  0)*(x22)
(x43) (valfin-a33) ( 0 -1 -1 -1) (x33) ( 0  0 -1  0) (x23)
(x44) (valfin-a34) ( 0  0 -1 -1) (x34) ( 0  0  0 -1) (x24)

sau, facand calculele:
(x41) (b1) (c11 c12 c13 c14) (x11)
(x42)=(b2)+(c21 c22 c23 c24)*(x12)
(x43) (b3) (c31 c32 c33 c34) (x13)
(x44) (b4) (c41 c42 c43 c44) (x14)

Observatii: 
1. Matricea C NU depinde de valoarea finala valfin si nici de matricea initiala A, ci numai de m si n
2. Matricea C se poate calcula pas cu pas in O(m*n^2): avem m pasi, la fiecare pas
inmultind o matrice cu maxim 3 valori -1 pe linie, in ordine, restul 0 cu matricea precedenta (in O(n^2)),
inmultind o matrice cu un singur -1 pe o linie, in ordine, si restul 0, in O(n^2), si adunandu-le
(in O(n^2))
3. Matricea B depinde de valfin si de matricea initiala A si se poate calcula pas cu pas in O(m*n):
avem m pasi, la fiecare pas inmultind o matrice cu maxim 3 valori -1 pe linie, in ordine, si restul 0 cu 
un vector coloana in O(n) si adaugand un vector coloana in O(n)
4. x41=x42=x43=x44=0, trebuie sa fie nule, pentru ca pe linia m+1 nu adaugam nici o valoare

Avem -B=C*X(1), unde X(1) este vectorul coloana
(x11)
(x12)
(x13)
(x14)

Observatie: pentru a avea solutie la problema initiala, trebuie ca -B=C*X(1).
Aceasta e o conditie necesara. De asemenea, aceasta e o conditie suficienta,
deoarece putem determina toti X(ij) cunoscand X(1) si ei corespund la o solutie.
X(1) trebuie sa fie facut din intregi, pentru a respecta conditia ca solutia
sa fie intreaga.

Calculam descompunerea LUP a lui C, in O(n^3), ca in [CLR], sectiunea 31.4.
Pentru fiecare valfin de la 0 la 1000, calculam B (O(m*n)), 
si calculam solutia X(1) (O(n^2), pentru ca avem descompunerea LUP a lui C). 
Daca x(1j) este intreg, am obtinut o solutie, altfel trecem la urmatoarea valfin.

Se foloseste propozitia din [CLR], care zice ca daca avem descompus C in LUP, putem
calcula X in O(n^2), pentru B variabil.

Complexitatea: O(m*n^2+n^3+valfin*m*n+valfin*n^2)

Autor: Liviu Lalescu

[CLR]=Cormen, Leiserson & Rivest, Introducere in Algoritmi
[GInfo]=Gazeta de informatica