Polar_'s blog

[Help] Counting Towers CSES
By Polar_, history, 5 years ago, In English

Hi Everyone ! I am not able to understand how to break this problem into subproblems ?
Can someone help please ? Here is the problem link : Problem

Tags dp, cses
  • Vote: I like it
  • +2
  • Vote: I do not like it

Comments Comments (8)
| Write comment?
»
5 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Just Bumping it . In case someone wanna help .

→ Reply
»
5 years ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

Think about the last row of the tower. You can either have both cells as a part of the same block, or both cells as parts of different blocks. Let's call towers of the first kind type-1 towers, and the towers of the second kind type-2 towers.

Let's call $$$a_n$$$ be the number of type-1 towers and $$$b_n$$$ be the number of type-2 towers.

For computing $$$a_n$$$, look at what remains when you remove the last row from the tower. Corresponding to a type-1 tower of height $$$n - 1$$$, there will be two such towers, and corresponding to a type-2 tower of height $$$n - 1$$$, there will be one such tower, so $$$a_n = 2a_{n - 1} + b_{n - 1}$$$. In a similar manner you have $$$b_n = 4b_{n - 1} + a_{n - 1}$$$.

Then you can either precompute the answers to all possible queries, or use matrix exponentiation to solve the recurrence. The answer is $$$a_n + b_n$$$.

→ Reply
  • »
    »
    5 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    Thanks a lot .

    → Reply
  • »
    »
    4 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    When computing bn, you consider the last row to build the type-2 tower right ? But I don't understand why it can be 4 * b(n-1) + a(n — 1) sir. Thanks you if you can explain to me!!

    → Reply
    • »
      »
      »
      4 years ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      Because the lower n-1 level can have either one a[n-1] and one b[n-1] because of solid border, or 2 b[n-1] breaking any of the borders, and b[n-1] when breaking both the borders. Here border is the line between the nth and (n-1)th row.

      → Reply
  • »
    »
    2 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    I don't understand the explanation of the type-1 and type-2 block, can someone give me and example? thanks

    → Reply
»
5 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

can someone tell me the rating of this problem acc to codeforces

→ Reply
»
17 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

I came up with another solution which I think is easier to understand (obvs im biased)

Call a "floor" a tower that can't be split horizontally. A floor of size n can be a 2xn block (1 way) or two 1xn blocks next to eachother such that the two blocks are never broken on the same layer. The second type of floor has n-1 layers. Each can be broken to the left, the right, or not broken at all ($$$3^{n-1}$$$) ways, which means the number of floors of size n is $$$f_n = 1 + 3^{n-1}$$$

All towers of size n are made of a tower size j, with a floor of size n-j on top. Thus, the number of towers size n is $$$\displaystyle t_n = \sum_{j=0}^{n-1} t_j f_{n-j}$$$. This takes $$$O(n^2)$$$ time to calculate, so we simplify:

$$$ \displaystyle t_n = \sum_{j=0}^{n-1} t_j (1 + 3^{n-j-1}) $$$
$$$ \displaystyle = \sum_{j=0}^{n-1} t_j + \sum_{j=0}^{n-1} t_j 3^{n-j-1} $$$
$$$ \displaystyle = p_n + 3 \sum_{j=0}^{n-2} t_j 3^{n-j-2} + t_{n-1} $$$
$$$ \displaystyle = p_n + 3(t_{n-1} - p_{n-1}) + t_{n-1} $$$

where $$$p_n$$$ is a prefix sum

This was my code:

vector<ll> towers(maxN+1), psum(maxN+1);
towers[1] = 2;
psum[1] = 1;
for (int i = 2; i <= maxN; i++) {
	psum[i] = (psum[i-1] + towers[i-1]) % MOD;
	towers[i] = psum[i] + 3*(towers[i-1] - psum[i-1]) + towers[i-1];
	towers[i] = (towers[i] % MOD + MOD) % MOD;
}
→ Reply