Counting Towers Recurrence Verification From CSES Problem Set

Question

Problem Statement:

Your task is to build a tower whose width is 2 and height is n. You have an unlimited supply of blocks whose width and height are integers.

For example, here are some possible solutions for n = 6:

Given n, how many different towers can you build? Mirrored and rotated towers are counted separately if they look different. Input The first input line contains an integer t: the number of tests. After this, there are t lines, and each line contains an integer n: the height of the tower.

Output:

For each test, print the number of towers modulo 10^9+7.

Example

Input:

3

2

6

1337

Output:

8

2864

640403945

My Approach:

Consider a function Fun(h, w), where h and w stand for height and width respectively, I assume that this function recursively works and returns me the number of ways to count towers for the respective parameters.

The two subproblems I identified:

• Find the number of towers of height 'h - 1' and of the same width. That function is Fun(h - 1, w). The last height has the block size of 1x2, this can be filled in two ways, two 1x1 blocks and one 1x2 block. So by fundamental prinicpal of multiplication the number of such towers is 2*Fun(h-1, w) by fixing the width.
• Now we keep our height constant and modify our width, the recurrence I obtained here was Fun(h, w-1) * Fun(h, 1). Basically find the number of ways of constructing a tower of width 1 and height h and number of ways of constructing a tower of height h and width w - 1. On applying fundamental principle of multiplication we get the number of ways as Fun(h, w-1) * Fun(h, 1).

Finally my recurrence looks like this:

Fun(h, w) = 2 * Fun(h - 1, w) + Fun(h, w - 1) * Fun(h, 1)
if h == 0 or w == 0 return 0;
if h == 1 and w == 2 return 2;
if h == 2 and w == 1 return 1; // trivial base cases

I wanted to know whether the recurrence I have designed is valid or not, this seems to work well for h = 2 and w = 2 but fails for the rest, what am I missing here? Please try to explain.

Answer 1

There are several problems in your recurrence:

• for $h = 0$ or $w = 0$, there should be one possibility, not zero: the only way to build a tower of height or width zero is adding no block at all;

• you write:

  Find the number of towers of height 'h - 1' and of the same width. That function is Fun(h - 1, w). The last height has the block size of 1x2, this can be filled in two ways, two 1x1 blocks and one 1x2 block.

  but if you are considering block size 1×2, that means that you are implicitly considering $w = 2$, which is not necessarily the case;

• you are not considering the possibility to add a (for example) $2\times 2$ block at the top of the tower, in the case $w = 2$.

What I would suggest:

• write a function to compute the number of possibilities for a tower of width $1$ and height $H$, independently (this is easier to write and can serve as a preliminary exercise). Let us denote this function $f_1(H)$;
• to build a tower of height $H$ and width $2$, for $H> 0$, you have to consider two cases:
  • if there are no block of width $2$, there are $f_1(H)^2$ possibilities to construct the tower (two towers of width $1$ and height $H$);
  • if the top block of width $2$ that appears in the tower starts at height $h\geqslant 0$ and has height $k$, we have to complete with two towers of width $1$ and height $H - h - k$, over one block $k\times 2$ over a tower of height $h$ and width $2$. That means: $$f_2(H) = \sum\limits_{h=0}^{H-1}\sum\limits_{k=1}^{H-h}f_2(h) \times f_1(H-h-k)^2$$