My 2nd Problem for HackerRank // Puzzle and PC

Problem statement

You are given a square NxN board divided into single cells, where N is always a power of 2. You are also given an infinite number of L-shaped trominoes:

tromino

Note that each tromino can covers three cells.

The board has one special cell S on which you are not allowed to place any tromino. Your task is to cover the whole board with trominoes in such a way that any two trominoes don't overlap, and every cell (except cell S) is covered by some tromino.

The full problem is available here: https://www.hackerrank.com/contests/lambda-calculi-sep14/challenges/puzzle-and-pc

Solution

This problem can be quite a tough at the beginning but as soon as you notice that it can be solved by a divide and conquer approach you can be really satisfied. The big hint here is that the size of the board is always a power of 2.

Lets start with the base case when n is 0. We have then a 1x1 board with one special cell so we don't have to do anything here :)

Lets now assume that n > 0, so we have at least 2x2 board. Lets divide it in 4 equal parts as in the below picture:

2

One and only one of this parts contains the special cell, lets call this part P. Now the crucial thing, if we place a block in the middle of the board in such a way that it covers 3 co corners of all parts other than P we can solve a problem recursively in all parts separatelly. The reason for this is that each part is half a size of the input board and contains exactly one already covered cell - part P contains the special cell S and we jest cover one corner of any other part - check the below picture:

1

The time complexity here is linear because on each level of recursion we do a constant time work, so T(n) = 4 * T(n/4) + O(1) which is O(n).

  • http://blog.hobbycoding.web.id Ruly Anggriawan

    nice solution. thanks