Phi 2012 Codility Programming Certificate Solution
Before we solve the main problem, let us consider a similar but much simpler problem. Aboard is given. In how many different ways can we cover it using domino tiles? Let us denote this number by . For there is only one way to do it ( ). For there are two symmetrical ways to do it ( ). For it can be done in three different ways ( ), but for there are five (not four) different ways to cover the board ( ), as shown in a figure below.
- If there is a horizontal tile at the top of the board, then the number of such solutions equals ;
- If there are two vertical tiles at the top of the board, then the number of such solutions equals .
One of the fastest ways to calculate the Fibonacci numbers is to use matrix exponentiation. Let us define:
Let's get back to the main problem. We deal with anboard (where ) and cover it with and tiles. Again, imagine that we cut the board with a horizontal line. The line can hit some tiles. When merging all possible coverings of the parts of the board above and below the line, we should consider all possible configurations of the tiles crossed by the horizontal line. Such configurations can be represented by bit vectors of length . Since , there are at most 128 such vectors. Of course, not all of them are feasible. If 1s represent crossed tiles, then they must appear in sequences of even length. The following function defines the integers (from 0 to ) whose binary representations are feasible bit vectors:
def feasible(x): ok= True while(x > 0): if x % 2 == 1: ok = not ok elif not ok: return False x = x//2 return okImagine that there are two horizontal lines crossing the board such that there is exactly one row of squares between them. These lines can cross some tiles, but at each horizontal position at most one of them can cross such a tile. Simply, if one line crosses a tile, then the other one is adjacent to its side. Let and be non-negative integers, such that and their binary representations are feasible bit vectors. When is it possible that they represent positions where the two horizontal lines cross the tiles? Only if 1s in their binary representations appear at disjoint positions. On the other hand, if it is possible, then there is only one way to do it—all free squares between the horizontal lines must be covered by tiles. The following procedure defines a matrix , such that if and only if and represent a possible combination of tiles crossed by the two horizontal lines, and otherwise.
def row_matrix(M): mm=2**M A = [*mm for i in xrange(mm)] for i in xrange(mm): if feasible(i): for j in xrange(mm): if feasible(j) and (i & j) == 0: A[i][j] = 1 return AIf there are rows of squares between the two horizontal lines, and and represent tiles crossed by the two horizontal lines, then, in the same way as in the simpler problem analyzed at the beginning, there are ways to cover the squares between the two lines. Hence, there are ways to cover the board so that no tile extends the upper or lower edge of the board. All we lack to solve the task is a matrix multiplication (modulo 10,000,007):
def ident(size): Id = [*size for i in xrange(size)] for i in xrange(size): Id[i][i] = 1 return Id def matrix_mult(A, B, ModRes): size = len(A) C = [*size for i in xrange(size)] for i in xrange(size): for j in xrange(size): cc = 0 for k in xrange(size): cc = (cc + (A[i][k] % ModRes) * (B[k][j] % ModRes))% ModRes C[i][j]= cc return C def matrix_exp(A, N, ModRes): size = len(A) B = ident(size) while N > 0: if N % 2 == 1: B = matrix_mult(A, B, ModRes) A = matrix_mult(A, A, ModRes) N = N//2 return B def count_tilings(N, M): B = matrix_exp (row_matrix(M), N, 10000007) return BMatrix exponentiation requires matrix multiplications. The latter ones run in cubic time. Since we deal with matrices, the overall time complexity is .