# Monthly Archives: September 2014

I'm really excited, because I've just received the award for my performance in the Addepar Hackaton.

I just want to mention that Addepar service is amazing. I asked for a white T-shirt, which wasn't available, but they managed to fulfill that request. In addition, Michelle sent me a nice personal note

Check the photos below, the T-shirt is really cool (much better than an usual tech company T-shirt):

# My 3rd Problem for HackerRank // Towers

## Problem statement

You're given infinitely many bricks of at most 15 different heights (other dimensions are not relevant here). You're also given a big integer $n$. The task is to count the time needed to build every possible tower of height N from the given bricks. Bricks are stacked vertically only and stand in an upright position. Two towers are different if their brick height sequences are different and building one tower takes exactly 2 time units regardless of its height.

Here is the full problem statement.

## Solution

In the editorial I omit the fact that we have to count the time needed to build all towers - we will count here just the number of different towers and to get the result, you have to multiply this number by 2.

### Simpler problem first

There is a restriction, that every bricks is of height at most 15 and $N$ is at most $10^{18}$. Lets first try to solve a simpler problem and assume that there are only bricks of height 1 or 2 and $N \leq 10^6$.

Let $f_n$ be the number of different towers of height $n$ which can be build of given bricks. In our simpler problem we have:

$f_1 = 1$, because there is only one tower of height 1 consisting of one bricks of height 1

$f_2 = 2$, because there are exactly two towers of height 2 - one consisting of two bricks of height 1 and the other consisting of one brick of height 2

We can now give a recursive definition for $f_n$ when $n > 2$:

$f_n = f_{n - 1} + f_{n - 2}$

because we can get one unique tower of height $n$ by placing a brick of height 1 on any tower of height $n - 1$ and one unique tower of height also $n$ by placing a brick of height 2 on any tower of height $n - 2$.

If we compute $f_n$ bottom-up (like in dynamic programming) rather than using recursion explicitly, we can do it in $O(n)$ time which is fine if $n$ is not as big as in the problem statement.

### Removing heights restriction

Lets remove the first restriction, so we have to deal now with bricks of at most 15 different heights (from 1 to 15).

Let $h_i$ indicates whether we have a brick of height $i$:

then the general recursion equation is:

$f_n = 0$ for $n < 0$

$f_0 = 1$

$f_n = h_1 \cdot f_{n - 1} + h_2 \cdot f_{n - 2} + h_3 \cdot f_{n - 3} + \ldots + h_15 \cdot f_{n - 15}$ for $n > 0$

### Solving the original problem

The last thing that we have do deal with is the really big $n$ - up to $10^{18}$. We will do it defining the recursive equation as a matrix multiplication problem and solve it using fast matrix exponentiation.

Lets assume that we've computed $f_n$ for $n \leq 15$ using dynamic programming and let $M$ be a $15 \times 15$ matrix defined as follows:

$M = \begin{bmatrix}0&1&0&0&0&0&0&0&0&0&0&0&0&0&0\\0&0&1&0&0&0&0&0&0&0&0&0&0&0&0\\0&0&0&1&0&0&0&0&0&0&0&0&0&0&0\\0&0&0&0&1&0&0&0&0&0&0&0&0&0&0\\0&0&0&0&0&1&0&0&0&0&0&0&0&0&0\\0&0&0&0&0&0&1&0&0&0&0&0&0&0&0\\0&0&0&0&0&0&0&1&0&0&0&0&0&0&0\\0&0&0&0&0&0&0&0&1&0&0&0&0&0&0\\0&0&0&0&0&0&0&0&0&1&0&0&0&0&0\\0&0&0&0&0&0&0&0&0&0&1&0&0&0&0\\0&0&0&0&0&0&0&0&0&0&0&1&0&0&0\\0&0&0&0&0&0&0&0&0&0&0&0&1&0&0\\0&0&0&0&0&0&0&0&0&0&0&0&0&1&0\\0&0&0&0&0&0&0&0&0&0&0&0&0&0&1\\h_{15}&h_{14}&h_{13}&h_{12}&h_{11}&h_{10}&h_9&h_8&h_7&h_6&h_5&h_4&h_3&h_2&h_1\end{bmatrix}$

Let $V$ be the following vector:

$V={\begin{bmatrix}f_1&f_2&f_3&f_4&f_5&f_6&f_7&f_8&f_9&f_{10}&f_{11}&f_{12}&f_{13}&f_{14}&f_{15}\end{bmatrix}}^T$

if we multiply $M \cdot V$ we get:

$R={\begin{bmatrix}f_2&f_3&f_4&f_5&f_6&f_7&f_8&f_9&f_10&f_{11}&f_{12}&f_{13}&f_{14}&f_{15}&f_{16}\end{bmatrix}}^T$

and we can return $f_{16}$ from here, so in order to compute $f_n$ for $n > 15$ we can compute:

R = \underbrace{(M \cdot (M \cdot \dots \cdot (M}_{n - 15} \cdot V)))

which can be written in the following form, because matrix multiplication is associative:

R = M^{(n-15)} \cdot V

and we can compute $n$-th power of a matrix of size $m \times m$ it $O(m^3 \cdot \log_2 {n})$ using fast exponentiation by squaring and in our problem we have $m = 15$ and $n \leq 10^{18}$ which is perfectly fine in terms of time limits. One speedup here can be to do exponentiation iteratively rather than recursively

# 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:

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:

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:

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).

# My 1st Problem for HackerRank // Bangalore Bank

I'm really happy because this is my first problem which I set for HackerRank. The problem was a part of Functional Programming Contest - September'14

## Problem statement

The original problem statement is available here and I really encourage you to check it there. The short story is that you have to insert n numbers on a standard computer keyboard (without a numpad) using only two fingers in an optimal time. The time of pressing a single key is 1 and the time needed to move a finger from on key to another equals the distance between these two keys. In addition, initially you can place the fingers anywhere you want.

## Solution

First of all, lets notice that we can ignore time needed for pressing keys during computation and add it while printing the result, since if we have to just press n keys, we have to spend n seconds for it.

It's tempting to assume that it's optimal to initially place fingers on the first two keys in the sequence or to assume that the optimal solution can always move the closest finger to handle the next key. Neither of these is correct. In order to proof that the first one is wrong, lets consider the following input: 1, 2, 9. If you place fingers initially on 1 and 2 the overall cost (remember we don't count time needed for pressing keys here) equals 9 - 2 = 7, but if you place fingers initially on 1 and 9 it leads to overall cost 1. To show that the second assumption is wrong, lets assume that you're in the middle of the sequence and fingers are on keys 1 and 9. The remaining portion of the sequence is the following: 1 2 1 2 ... 1 2 repeated as many time as needed. If you always move the closest finger to handle the next key you will keep moving a finger from 1 to 2 back and forth, but a better solution is to move a finger from 9 to 2 and that's your overall cost for handling all the incoming input.

So what's the correct approach? Actually this problem is an offline version of one of the most famous problems in online algorithms called k-server problem. While an online version is really hard to solve, in order to real with an offline version a simple dynamic solution suffices.

Lets notice that fingers are indistinguishable, so it doesn't mather which one is left or right. Lets define $dp[n][a][b]$ is the optimal cost for handling a prefix of length $n$ of the input sequence in such a way that your fingers end up on keys $a$ and $b$. From the problem statement we know that $dp[0][a][b]$ equals 0 for all $a$ and $b$. Lets define the recurrence relation:

$dp[n][a][b] = \min_{x \in \{0, 1, \ldots, 9\}}(dp[n - 1][a][x], dp[n - 1][x][b])$

Clearly the answer is $\min_{a,b} dp[n][a][b]$

Time complexity of this solution is $O(n \cdot 10^3)$ and the correctness follows immediately from dp definition and the recurrence relation. In order to achieve that complexity in a functional programming approach a good idea is to memoize dp function.