The following problem was posed in 2000 in an e-mail contest in [GInfo]. The solution below
(O(n^3+valfin*n^2)) was about 100 times faster than the best known method until then, which
was O(valfin*n^3). But you need to use fractional numbers with larger precision if m>35 and
n>35. The original program won the most points (30 out of 100) for this problem and,
after it was verified by the editors of GInfo and, after correcting some bugs and adding
multiple precision, it solved correctly and fast all the tests. If you want the implemented
program, it is on http://lalescu.ro/liviu/rubik/ Please write to the author for questions
or comments (see http://lalescu.ro/liviu/ for the e-mail address).
Problem [GInfo]:
Given a matrix A with dimensions m*n (m and n between 1 and 100), with integers.
A sequence is adding an integer value in a position and the same value in each of the 2, 3 or 4 adjacent
positions (horizontally and vertically, but not diagonally). It is desired a succession of sequences
to lead to a matrix which contains in each position the same value, valfin, between
0 and 1000.
Solution:
Let A be the input matrix, with dimensions m*n
Let X be the solution matrix, with dimensions m*n, where (x11) is added to a(11) and the neighbours:
a(12) and a(21), ...., m(mn) is added to a(mn) and to the neighbours: a(m,n-1) and a(m-1,n).
Let valfin be the value which is obtained everywhere in the matrix, 0<=valfin<=1000
Let m=4, n=3 (example)
The initial matrix is:
a11 a12 a13 a14
a21 a22 a23 a24
a31 a32 a33 a34
After applying the matrix X (solution) to A, we have:
valfin valfin valfin valfin
valfin valfin valfin valfin
valfin valfin valfin valfin
Where:
For position 11: valfin=a(11)+x(11)+x(12)+x(21)
For position 12: valfin=a(12)+x(11)+x(12)+x(13)+x(22)
For position 13: valfin=a(13)+x(12)+x(13)+x(14)+x(23)
For position 14: valfin=a(14)+x(13)+x(14)+x(24)
Suppose we know x(11), x(12), ... x(1n) (the first line of solution X)
It results:
For position 11: x(21)=valfin-a(11)-x(11)-x(12)
For position 12: x(22)=valfin-a(12)-x(11)-x(12)-x(13)
For position 13: x(23)=valfin-a(13)-x(12)-x(13)-x(14)
For position 14: x(24)=valfin-a(14)-x(13)-x(14)
Which means:
(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)
(a column vector is equal to the sum between a column vector and a 4*4 matrix multiplied with a column vector)
So we know the second line of the solution, if we know the first line.
Analogously,
(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)
Analogously,
(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)
or, making the calculations:
(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)
Observations:
1. The matrix C does NOT depend on the final value valfin or on the initial matrix A,
but only on m and n
2. The matrix C may be calculated step by step in O(m*n^2): we have m steps, at each step
multiplying a matrix with maximum 3 values of -1 on the line, in order, the rest are 0,
(in O(n^2)), multiplying a matrix with one value of -1 on the line, in order, the rest
are 0, (in O(n^2)), and them together (in O(n^2)).
3. The matrix B depends on valfin and on the initial matrix A and can be calculated
step by step in O(m*n): we have m steps, at each step adding a matrix with at most 3 -1 values
on the line, in order, and the rest 0, with a column vector in O(n) and adding a column vector
in O(n)
4. x41=x42=x43=x44=0, they have to be zero, because on the line m+1 we do add no value
We have -B=C*X(1), where X(1) is the column vector
(x11)
(x12)
(x13)
(x14)
Observation: to have a solution to the initial problem, we need that -B=C*X(1).
This is a necessary condition. Also, this is a sufficient condition, as we
can determine all the X(ij) knowing X(1) and they correspond to a solution.
X(1) has to be composed of integers, to respect the integer condion of
the solution.
We compute the LUP decomposition of C, in O(n^3), like in [CLR], section 31.4
For each valfin from 0 to 1000, we compute B in O(m*n), and compute
the solution X(1) in O(n^2), because we have the LUP decomposition of C.
If x(1j) is integer, we have a solution, otherwise we get to the next valfin.
We use the proposition in [CLR], which says that if we have decomposed C in LUP, we
can compute X in O(n^2), for a variable B.
Complexity: O(m*n^2+n^3+valfin*m*n+valfin*n^2)
Author: Liviu Lalescu
[CLR]=Cormen, Leiserson & Rivest - Introduction to Algorithms
[GInfo]=Gazeta de informatica (in Romanian)