Wednesday, July 25, 2012

Tau 2012 Codility Programming Certificate Solution

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



Tuesday, July 24, 2012

Unfortunately, there was an error in the current certificate statement. On one hand, one can read that the input array A is non-empty. On the other hand, it is specified that the array's size N belongs to the range [0..100,000]. Also, the tests included an empty array.

We apologize for this mistake. The erroneous test has been removed and the specification of N has been corrected.

Codility team

Change in Codility Certificate expiration date

Following feedback from our followers, we have decided to make some changes to our Codility Certificate. We know it is not easy to get, so from now the efforts you make will be visible on Codility badge for much longer.

We are pleased to announce that the Codility Certificate you have gained today will be valid for 2 YEARS!

If you have any other ideas on how we can improve, send us your feedback on UserVoice.