# Cut a Strip Editorial - my hard problem in HackerRank Week of Code 36

Hello,

Recently HackerRank Week of Code 36 took place and two my problems were there:

Ways to give a check

Cut a Strip

I hope you had a fun time solving them!

Several people messaged and asked to share my approach to Cut a Strip problem (for some reason HackerRank hasn't published my editorial yet). So I decided to describe my approach here:

If you're not familiar with the problem yet, please read the statement here: Cut a Strip

Editorial

First of all, let's make some observations, which make the task easier to implement:

The first observation is that we can reduce the original problem, to the problem where we are allowed to cut only horizontal strips, i.e. ones with size $1 \times x$. This reduction is possible because if we have a solution only for horizontal strips, the vertical strips can be handled by rotating the input grid 90 degrees either way and solving the problem for horizontal stripes on this rotated grid. Notice that any vertical strip in the original grid is then transformed to a horizontal strip in the rotated grid.

Next observation is that we can consider any pair of columns $x \leq y$ and reduce the problem to 1-dimensional problem. How to do that? For now, let's assume that we can't cut any strips and just want to find the maximum sum of a sub-grid. In order to do that, we can iterate over all pairs of columns $x \leq y$ and for each such pair define an array $b[1 \ldots n]$ such that $b[i] := \sum\limits_{j=x}^y A_{i,j}$ and then use Kadane algorithm to find the maximum sum of a subarray of $b$. Since we considered all pairs of columns, then we're finding indeed the maximum sum of any sub-grid of $A$.

If we can only adjust the above technique to handle cutting a horizontal strip, we have a solution.

Now comes the crucial observation leading to an elegant solution. Notice that cutting the best horizontal strip of size $1 \times x$ for $x \leq k$ corresponds to choosing exactly one of elements of the array $b$ defined above and subtracting from it a sum of the strip we want to cut. Notice that for fixed columns $x \leq y$ and value of $b[i]$ such a strip is a non-empty subarray of array $[A_{i,x}, A_{i, x+1}, \ldots, A_{i,y}]$ of size at most $k$. Furthermore, the best of such strips that can be cut has the minimum sum amongst all possible ones. Thus what we really want to do is to select one of the elements of the array $b$, let's say $b[i]$, and subtract from it the minimum sum of subarray which $b[i]$ covers.

All these values can be computed using dynamic programming techniques. For an exact implementation of this method please refer to my commented submission attached below.

Total time complexity is therefore $O(n^2 \cdot (n+m) + m^2 \cdot (n+m))$ since we are solving the problem twice (for original grid and the rotated grid).

For implementation details, you can see my commented code using the exact method described above.

Cheers,

Pawel

# Long Narrow City // My hard problem in Counter Code by HackerRank

It was great preparing a hard problem for Counter Code hosted by HackerRank. Competition was great, and during 24 hours 26 participants manage to solved it. This is the most detailed editorial that I have written so far.

The problem is available here: Long Narrow City

## Statement

Problem statement is quite clear, we are given a graph for which we have to count the number of its spanning trees, containing at most k distincted roads. $k$ can be any number in range $[0, 200]$ and there are at most $1000$ distincted roads given in the input.

However, the graph can be really huge! It can have up to $3 \cdot 10^{12}$ vertices - definitely way too big to store them in the memory.

The good news is that is has a very specific structure. As the name of the problem suggests, it is very long, but fortunately a narrow one

Specifically, it has $3$ layers: top, middle and bottom, each consisting of $N$ vertices. Layers along with graph edges are presented in the below drawing. Notice, that there are $N$ edges between consecutive layers and each layer contains $N - 1$ internal edges:

Now we know what we are dealing with, so let's start solving it. What I like often to do, is to start with some simpler problem, derive a solution to it, and then adapt it further to the original problem. Let's give it a try here!

## Simplified problem

First, let's assume that there are no distincted edges.

### Simplified graph

Moreover, let's assume, that the graph has only $2$ layers instead of $3$. It is even more narrow, isn't it? From now we are referring only to simplified graphs unless we call the graph original explicitly.

Our simplified graph looks like this:

Since we assumed that there are no distincted edges, our task is to find the number of all spanning trees of it.

First, let's define what a segment it our narrow graph is. We call a segment a set of $3$ vertices with numbers $i, i + N, i + 2N$ for original graph, and a set of $2$ vertices with numbers $i, i + N$ for a simplified one.

An example segments, for original graph and simplified graph, are presented it the below drawing. Green vertices belong to the current segments, while red ones belong to the previous ones. Edges connecting these segments are also presented:

Let tail be the last segment of the graph.

Now we are ready to count the number of spanning trees of simplified graph. A great way to do that, is to try to extend a solution for a smaller graph by adding a new segment to it as a tail.

Let $G_{N}$ be a simplified graph with $3 \cdot N$ vertices. We can extend $G_{N}$ to $G_{N + 1}$ by adding a new segment to it and connect it to the tail of $G_N$.

This is the incremental method to build our graphs.

In order to count the number of spanning trees of $G_{n + 1}$, let's assume that we know the number of spanning trees of $G_{N}$. How does it help? Well, let $T_{N}$ be any spanning tree of $G_N$. We can extend $T_N$ to a spanning tree of $G_{N+1}$ by adding some edges of the tail of $G_{N+1}$ to $T_N$.

The crucial observation is that we can count spanning trees incrementally as well.

But be aware here. Does any spanning tree of $G_{N+1}$ can be produced from a spanning tree of $G_{N}$? Let's consider the below drawing presenting a valid spanning tree of $G_3$.

If you look closely, you will notice that this spanning tree cannot be produced from any spanning tree of $G_4$, because vertices $2$ and $5$ are connected in it through the tail of $G_5$.

However, the good news is that it can be producted from a spanning forest of $G_4$ with two connected components in which the top layer is the first connected component and the bottom layer is the second connected component. What is more important, the following fact is true:

Every spanning tree of $G_{N+1}$ can be produced by extending a spanning tree of $G_N$ or a spanning forest of $G_N$, in which top and bottom layers are different connected components, by adding a new layer and connecting it with some edges to the previous structure.

This is true, because in any valid spanning tree of $G_{N+1}$, vertices $N$ and $2N$ have to be connected by exactly one path. They can be connected by a path which does not use vertices $N + 1$ and $2N + 1$ or by a path which uses them. In the first case, the T_{N+1} is formed from $T_N$, while is the second case, it is formed from a forest of $G_N$ in which the top and the bottom layers are distinct connected components.

This is a good news, because we can count the number of spanning trees of $G_{N+1}$ by just knowing the number of spanning trees of $G_N$ and the number of specific spanning forests of $G_N$.

Let $T(N)$ be the number of spanning trees of $G_N$ and $F_N$ be the number of spanning forests of $G_N$ in which top and bottom layers are distinct connected components. In order to get the exact equation for $G_N$, we have to examine below cases and count the number of possible extensions in each case.

1. Any $T_N$ can be extended to $T_{N+1}$ in $3$ different ways, because we can add any $2$ of $3$ edges which are adjacent to vertices from the last segment of $G_{N+1}$
2. Any $F_N$ can be extended to $T_{N+1}$ in just one way, because we have to add all $3$ edges adjacent to vertices from the last segment to $G_{N+1}$.
3.  Any $T_N$ can be extended to $F_{N+1}$ in $2$ ways, because we have to add just one horizontal edge adjacent to vertices from the last segment of $G_{N+1}$ to $T_N$ and there are two ways to do that.
4. Any $F_N$ can be extended to $F_{N+1}$ in just one way, because we have to add $2$ horizontal edges adjacent to vertices from the last segment of $G_{N+1}$ to $F_N$ .

Let $T(N)$ be the number of valid graphs of type $T_N$ and $F(N)$ be the number of valid graphs of type $F_N$.

Clearly, $T(1) = 1$ and $F(1) = 1$. From the above analysis, we know that:

$T(N + 1) = 3 \cdot G(N) + F(N)$

$F(N + 1) = 2 \cdot G(N) + F(N)$

These two equations helps us to compute the number of spanning trees of simplified graphs.

### Original graph

That is great, but what does it have to do with our original graph with $3$ layers of vertices? Well, the same analysis works, but we have more cases to consider. From now we are referring to original, $3$ layer graphs, unless we call the graph explicitly simplified.

First some definition, which will helps us to refer to some things.

Let $i, i + N, i + 2N$ be vertices in the last layer of $G_N$. We define the following graphs:

Let $F^1_N$ be a spanning forest of $G_N$, in which vertex $i$ belongs to one connected component, vertices $i + N$ and $i + 2N$ belong to the other one, and there are only two connected components in this forest.

Let $F^2$ be a spanning forest of $G_N$, in which vertex $i + N$ belongs to one connected component, vertices $i$ and $i + 2N$ belong to the other one, and there are only two connected components in this forest.

Let $F^3_N$ be a spanning forest of $G_N$, in which vertex $i + 2N$ belongs to one connected component, vertices $i$ and $i + N$ belong to the other one, and there are only two connected components in this forest.

Let $F^0_N$ be a spanning forest of $G_N$, in which vertices $i, i + N, i + 2N$ belong to 3 different connected components, and there are 3 connected components in this forest

$T_N$ is defined as before, i.e. it is a spanning tree of $G_N$, so all vertices $i, i + N, i + 2N$ belong to the only connected component.

All $5$ above graphs are presented below - vertices belonging to the same connected component have the same color and there are as many connected components as colors of vertices in the last segments (notice that I did not draw any edges between these vertices just for generality - we don't assume by what path they are connected, we just indicate that they are connected - might be by direct edges and might be by longer paths):

Let also $F_1(N), F_2(N), F_3(N), F_0(N), G(N)$ be the number of graphs of corresponding types defined just above.

Based on these values, we can compute $G(N + 1)$ in a similar way that we did it in for simplified graphs. There are just more cases to consider and each of the above $5$ functions has its own recursive relation. The exact relations are presented below. You can compute them either by hand or write a small program to do it for you. I decided to do it by hand first and then double check it by a program:

$T(N + 1) = 8 \cdot T(N) + 3 \cdot F_1(N) + 4 \cdot F_2(N) + 3 \cdot F_3(N) + 1 \cdot F_0(N)$
$F_1(N + 1) = 4 \cdot T(N) + 3 \cdot F_1(N) + 2 \cdot F_2(N) + 2 \cdot F_3(N) + 1 \cdot F_0(N)$
$F_2(N + 1) = 1 \cdot T(N) + 0 \cdot F_1(N) + 1 \cdot F_2(N) + 0 \cdot F_3(N) + 0 \cdot F_0(N)$
$F_3(N + 1) = 4 \cdot T(N) + 2 \cdot F_1(N) + 2 \cdot F_2(N) + 3 \cdot F_3(N) + 1 \cdot F_0(N)$
$F_0(N + 1) = 3 \cdot T(N) + 2 \cdot F_1(N) + 2 \cdot F_2(N) + 2 \cdot F_3(N) + 1 \cdot F_0(N)$

You have to derive values to $T(0), F_1(0), F_2(0), F_3(0), F_0(0)$ also.

Having these relations, we are able to compute the number of spanning trees of our graphs of any reasonable size. Even if $N$ is as big as $10^{12}$, we can still use matrix exponentiation to do that quickly.

So far so good, but remember that we simplified the problem to not having any distincted edges. Let's now get back to our original problem.

## Original problem

In the original problem, we have at most $1000$ distincted edges and we want to know the answer to how many spanning trees of $G_N$ are there, such that they have at most $k$ distincted edges, where $k$ is at most $200$.

How do deal with that problem? Well, do you remember how we extend, let's say $F^1_N$ to $T_{N+1}$? From the recursive equations derived before, we know that there are $3$ ways to do that i.e. there are $3$ subsets of edges forming a segment such that you can connect them to the tail of any $F^1_N$ to form a valid $T_{N+1}$. Let's call the st of these subsets $S$.

Let's also define $F^1_{N,a}$ as $F^1_N$ with exactly $a$ distincted edges. Similarly we define $T_{N,a}$ and so on. Let's pick any subset of edges in $S$, call it $s$, and assume that $s$ has $d$ distincted edges.

The crucial observation here is that we can form a valid $T_{N, a + d}$ from any F^1_{N, a} by adding edges from $s$ to $F^1_{N, a}$.

Based on these observations we can implement a dynamic programming solution to the the problem.

Let $\text{dp}_{T,k,N}$ be the number of spanning trees of $G_N$ with exactly $k$ distincted edges.

Similarly we define $\text{dp}_{F_1,k,N}$, $\text{dp}_{F_2,k,N}$, $\text{dp}_{F_3,k,N}$ and $\text{dp}_{F_0,k,N}$

Then we can compute any of above tables iterating over each segment in the graph, then iterating over each possible subset of edges in this segment and extending the solution to the larger graphs by examining how many distincted edges this subset has and to what kind of graph this subset extends our current graph (if it extends to any). You can precompute the extension table, i.e. precompute if a graph of type, let's say F_1 can be extended to, let's say F_3, using a particular subset of edges.

However, since $N$ is up to $10^{12}$ we are not allowed to iterate over all segments in the graph. Think for a second, do we really need to do this? Of course we don't. Notice that there are at most $1000$ distincted edges in the input, so there are also at most $1000$ segments with any distincted edge, which is like nothing comparing it to the $10^{12}$ possible segments. What we can do instead, is to assign distincted edges to segments to which they belong, sort this segments in increasing manner and process the graph from left to right. We have two cases to consider then:

1. The current segment has distincted edges.
In this case, we can use our dynamic programming method to extend the solution to the graph with one more segment.
2. The current segment is free of distincted edges.
In this case, we can see how far to the right is the next segment with distincted edges. Then we can use the recursive equation and matrix exponentiation, which are described in the simplifier problem, to extend the current solution to the segment just before the next segment with distincted edges. Since this method is pretty fast, we are able to skip over huge number of segments without dangerous edges very fast.

Notice that we are not allowed to store the whole $\text{dp}$ table anymore, because there are just too many segments. The good news is that we do not have to do this, because we just need to know the entry corresponding to the last examined segment. This reduces the space complexity a lot and is a common trick in these type of problems.

Since in the statement we are asked to answer questions on how many spanning trees with at most $k$ dangerous edges are for some values of $k$, we can now easily answer them based on our $\text{dp}$ tables, just by computing:

$\text{answer}_{N,k} = \sum_{m=0}^k \text{dp}_{T,N,m}$

where $\text{answer}_{N,k}$ is the number of spanning trees of the input graph with exactly $k$ distincted edges.

### Time complexity

First, you have to precompute the table of extensions, which stores the information if a graph of one type can be extended to a graph of another type using some particular subset of edges. Since there are $5$ types of graphs, $32$ subsets of edges, and you can compute the resulting graph for a given graph and subset of edges using $\text{dfs}$ this takes so small amount of time that we do not have to worry about it.

During the computations, sometimes you use skips by matrix exponentiation and since the matrix size if $5 \times 5$ and the longest skip has length $10^{12}$, one skip takes $O(5^3 \cdot \log(10^{12}))$.

At most $1000$ times we are forced to compute the extension of a current graph by dynamic programming, and doing this for one segment takes $O(5 \cdot 5 \cdot K \cdot 32)$, where $K$ is maximum number of distincted roads in a query. This is true, because in $\text{dp}$ table an entry for a graph of one type is based on values of every of $5$ other types of smaller graph and we compute the extension for any possible number of distincted edges. Computing one such entry takes 32 subsets of edges to consider. However this could be reduced by just examining the valid subsets of edges for a particular type of graph i.e. these ones which extends it to some other graph.

# My Editorials for CodeChef June Lunchtime 2015

It has been a while since I last wrote official editorials for CodeChef, but today was a great opportunity to do it. The June Lunchtime 2015 took place with four problems to solve. Two of them were very straightforward, while the other two require some knowledge to solve.

If you are interested in a quite clever dynamic programming problem, definitely check this problem Chef and Bitwise OR Operation.

All editorials are available here: Editorials

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