Tag Archives: recursion

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:

 h_i = \left\{ \begin{array}{l l} 1 & \quad \text{if we have bricks of height $i$}\\0 & \quad \text{if we don't have bricks of height $i$} \end{array} \right.

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:

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

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

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

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:

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

Hacckerrank Weekly #4 // problems 1-3

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 <a, b, k> 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.