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

# Palindrome Index

The first problem was posted on Monday. The statement says that you're give a string $s$ of $n \leq 10^5$ letters. The task is to find the index of a letter in the string such that after removing that letter $s$ is a palindrome. It's guaranteed that such an index exists. One test file consists of at most 20 test cases.

## Solution

There are two cases. The string $s$ can be already a palindrome or not.

It's easy to check, that if $s$ is already a palindrome, then after removing the $n / 2$-th letter, $s$ remains a palindrome.

If $s$ is not a palindrome, then there exists an index $i$ such that $s_i \neq s_{n - 1 - i}$. Let $k$ be the smallest such index.

Again, it's easy to see that we have to remove either $s_{k}$ or $s_{n - 1 - k}$, because after removing any $s_j$ for $k < j < n - 1 - k$, $s_{k}$ will be compared with the same letter that it was compared in the original $s$ and the result of that comparison is still negative. In addition, it makes no sense to remove any $a_j$ for $j < k$ or $j > n - 1 - k$ because with that action we won't achieve anything positive.

Let:

$a := s$ without $s_{k}$

$b := s$ without the $s_{n - 1 - k}$

From the problem statement, we know that at least one of $a$ and $b$ is a palindrome. If $a$ is a palindrome, then the result is $k$. In the other case, the result is $n - 1 - k$.

The time complexity of that solution is $O(n)$.

# Algorithmic Crush

In Tuesday problem, you're given an array $c[1..n]$, where $n \leq 10^7$. Initially $c_i := 0$ for each $i$.

Next, there are $m \leq 2 \cdot 10^5$ queries. Each query consists of 3 integers $a, b, k$, and it adds $k$ to every $c_i$ where $a \leq i \leq b$. Your task is to return the maximal value in the array after performing these $m$ operations. The full problem statement is here.

## Solution

At the first sight it seems like a segment tree problem, but it would be an overkill here. The crucial thing there is that we only have to compute a maximal value once, so we can first "perform" all queries and then calculate the result. The next simple observation is that we can only consider elements $c_i$ for which there is at least one query where $a$ or $b$ equals $i$. That observation led us to a solution based on sorting.

Let's thing of each query as of two event. Each event has it's own index and value. For the query $$ the first event is to add a value $k$ to the index $a$ and the second event is to subtract a value $k$ from the index $b$. After that, we can sort these events. We say that event1 < event2 iff. the index of event1 is less than the index of event2 or these indices are equal and event1 is the opening event i.e. it adds a value. Next we can process all the events from left to right keeping track of the current value and the maximum value. We update the maximum value if the current value is greater than the maximum value collected so far.

The total time complexity of that method is $O(m \cdot \log m)$ and it's worth to mention, that it doesn't depend on $n$ at all.

# Lucy and Flowers

Wednesday problem is more difficult, but not so much While the original problem statement has some story behind it, the real task is the following:

You're given $n \leq 5000$ distinct integers. The task is to count how many distinct Binary Search Trees (BST) can be created by picking any non-empty subset of these integers. Because the result can be very large, you have to compute it modulo $10^9 + 9$, but in order to provide a clear solution I'll omit that. There are at most $5000$ testcases in one test file.

## Solution

There are two crucial observations. If you pick two different subsets, the trees created from these subsets are different. On the other hand, if you pick two subsets with the same number of elements, the number of different trees created from each subset is the same, because only ranks of elements matter, not their relative values.

Let $dp[k]$ be the number of different BST that can be created from $k$ integers and assume that we can compute that value.

Then using two above facts, the result can be computed as:

$\sum\limits_{k = 1}^n = \binom {n} {k} \cdot dp[k]$

because we can compute the number of different BST for each subset separately and that number is the same for subsets of the same size.

But how to compute $dp[n]$ for any $n$?

If we have $n$ elements, we can put any of them in the root of a tree. If we put the $k$-th smallest of them, $k - 1$ smallest elements have to be in the left subtree of the root and $n - k$ largest elements have to be in the right subtree. The number of possible different BST as a left subtree is $dp[k - 1]$ and it's $dp[n - k]$ for the right subtree. This led us to the recursive formula:

$dp[n] = \sum\limits_{k = 1}^{n} dp[k - 1] \cdot dp[n - k]$

The base case is:

$dp[0] = 1$

because there is only one empty BST.

In the full solution, we precompute $dp$ table and binomial coefficients $\binom {n} {k}$. These two precomputations take $O(n^2)$ time. After that, we can compute every testcase in $O(n)$ time which gives $O(n^2 + t \cdot n)$ time, where $t$ is the number of testcases.