Another month has passed and it is time to show how the previous Codility Certificate,
codenamed
T (Tau), can be solved.
You can still give it a try, but no certificate will be granted.
This problem is a variant of a problem posed by J. Bentley in his
Programming Pearls.
The original problem was to find, in a given matrix, a rectangular region with a maximal sum of elements.
We will show how this original problem can be solved, and then we will extend the solution to
the certificate problem.
Expected time complexity of the solution is \(O(M^3+N^3)\), although a faster solution is known
(see
H. Tamaki and T. Tokuyama, 2000).
Let \(C\) be the given matrix of \(M \times N\) integers.
There are \(O(N^2 \cdot M^2)\) rectangular fragments of the matrix.
Moreover, a naïve way to calculate the elements in the rectangle requires \(O(N \cdot M)\) time.
To obtain the desired time complexity we have to reduce the number of rectangles considered,
and compute the sum of elements in a rectangle more quickly.
First, let us focus on the latter problem.
We can compute the sum of elements in a given rectangle in constant time,
after \(O(N \cdot M)\)-time pre-processing.
The idea is to compute another \((M+1) \times (N+1)\) matrix \(sum\), such that:
\[sum[x][y] = \sum_{i=0}^{x-1} \sum_{j=0}^{y-1} C[i][j]\]
Then, the sum of elements in \(C[i_1..i_2][j_1..j_2]\) equals:
\[sum[i_2+1][j_2+1] - sum[i_1][j_2+1] - sum[i_2+1][j_1] + sum[i_1][j_1]\]
For the time being, let us fix the indices \(0 \le i_1 \le i_2 < M\).
How can we find the maximal-sum rectangular submatrix \(C[i_1..i_2][j_1..j_2]\)?
Think about a one-dimensional array \(C'[j] = \sum_{i=i_1}^{i_2}C[i][j]\).
The sum of elements in \(C[i_1..i_2][j_1..j_2]\) is equal to the sum of elements in \(C'[j_1..j_2]\).
In this way, the problem reduces to another problem posed by Bentley: that of finding a maximal-sum contiguous fragment of a one-dimensional array.
What is interesting is that this problem can be solved in \(O(N)\) time.
So, by solving this one-dimensional problem for all possible \(O(M^2)\) pairs of indices
\(i_1\) and \(i_2\) we obtain an \(O(M^2 \cdot N)\) time solution of the two-dimensional problem posed by Bentley.
Now let us deal with the one-dimensional problem.
How can we find the maximal-sum contiguous fragment \(C'[j_1..j_2]\) of array \(C'\)?
Let us define array \(sum'\) as follows: \(sum'[j] = sum[i_2+1][j] - sum[i_1][j]\).
The sum of elements in \(C'[j_1..j_2]\) equals \(sum'[j_2+1] - sum'[j_1]\).
If we fix \(j_2\), what then is the optimal value of \(j_1\)?
Clearly, it is an index such that \(0 \le j_1 \le j_2\) and \(sum'[j_1]\) is minimal.
So, to find the optimal values of \(j_1\) and \(j_2\), it is sufficient to scan all possible
values \(sum'[j_2]\), keeping track of the minimum value \(sum'[j_1]\) found so far.
After solving the two-dimensional problem posed by Bentley, it is time to see how to extend
the solution for the certificate.
Each rectangular submatrix corresponds to not one but four rectangles on a torus.
In the following figure they are numbered from 1 to 4.
The solution presented so far finds the maximal-sum rectangle of type 1.
To find the maximal-sum rectangle of type 2 for given indices \(i_1\) and \(i_2\),
it is enough to find the minimal-sum rectangle of type 1.
To find the maximal-sum rectangles of type 3 or 4, one should use the following
array \(sum'\) instead: \(sum'[j] = sum[M][j] - sum[i_2+1][j] + sum[i_1][j]\).
The overall time complexity of the presented solution is \(O(M^2 \cdot N)\).
We can optimize it slightly, transposing the input matrix if \(M > N\).
This way, we obtain a solution running in \(O(\min(M,N)^3)\) time.
Here is an implementation of the presented solution in Python.
Arrays \(C'\) and \(sum'\) are not defined explicitly; equivalent
expressions referring to the array \(sum\) are used instead.
def torus_lot(C):
M = len(C)
N = len(C[0])
if M > N:
# Transpose C
C1 = [([0] * M)] * N
for j in range(N):
C1[j] = C1[j][:]
for i in range(M):
C1[j][i] = C[i][j]
C = C1
M = len(C)
N = len(C[0])
# sum[i][j] = profit of a rectangle [0..i-1]x[0..j-1]
sum = [([0] * (N+1))] * (M+1)
for i in range(1, M+1):
sum[i] = sum[0][:]
for j in range(1, N+1):
sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + C[i-1][j-1]
Res = 0 # Maximum profit of a rectangle
for i1 in xrange(M):
for i2 in xrange(i1+1, M+1):
Min1 = 0 # Minimum profit of a rectangle [i1..i2-1]x[0..j-1]
MinJ1 = 0 # Maximum such j
MaxP1 = 0 # Maximum profit of a rectangle [i1..i2-1]x[j'..j-1]
Max1 = 0 # Maximum profit of a rectangle [i1..i2-1]x[0..j-1]
MaxJ1 = 0 # Minimum such j
MinC1 = 0 # Minimum profit of a rectangle [i1..i2-1]x[j'..j-1]
Min2 = 0 # Minimum profit of a rectangle [0..i1-1,i2..M-1]x[0..j-1]
MinJ2 = 0 # Maximum such j
MaxP2 = 0 # Maximum profit of a rectangle [0..i1-1,i2..M-1]x[j'..j-1]
Max2 = 0 # Maximum profit of a rectangle [0..i1-1,i2..M-1]x[0..j-1]
MaxJ2 = 0 # Minimum such j
MinC2 = 0 # Minimum profit of a rectangle [0..i1-1,i2..M-1]x[j'..j-1]
for j in xrange(1,N+1):
Profit1 = sum[i2][j] - sum[i1][j]
if Profit1 <= Min1:
Min1 = Profit1
MinJ1 = j
if (Profit1 - Min1 > MaxP1):
MaxP1 = Profit1 - Min1
if Profit1 > Max1:
Max1 = Profit1
MaxJ1 = j
if (Profit1 - Max1 < MinC1):
MinC1 = Profit1 - Max1
Profit2 = sum[M][j] - Profit1
if Profit2 <= Min2:
Min2 = Profit2
MinJ2 = j
if (Profit2 - Min2 > MaxP2):
MaxP2 = Profit2 - Min2
if Profit2 > Max2:
Max2 = Profit2
MaxJ2 = j
if (Profit2 - Max2 < MinC2):
MinC2 = Profit2 - Max2
Res = max(Res, MaxP1, MaxP2, Profit1 - MinC1, Profit2 - MinC2)
return Res
