### Rendering_Engine's blog

By Rendering_Engine, history, 8 months ago,

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

• +2

 » 8 months ago, # |   0 Just Bumping it . In case someone wanna help .
 » 8 months ago, # |   +1 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$.
•  » » 8 months ago, # ^ |   0 Thanks a lot .
•  » » 6 weeks ago, # ^ |   0 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!!
•  » » » 5 weeks ago, # ^ |   0 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.
 » 5 months ago, # |   0 can someone tell me the rating of this problem acc to codeforces