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

Please read the new rule regarding the restriction on the use of AI tools. It applies starting from round 972.
×

# | User | Rating |
---|---|---|

1 | tourist | 4009 |

2 | jiangly | 3773 |

3 | Radewoosh | 3646 |

4 | ecnerwala | 3624 |

5 | jqdai0815 | 3620 |

5 | Benq | 3620 |

7 | orzdevinwang | 3612 |

8 | Geothermal | 3569 |

8 | cnnfls_csy | 3569 |

10 | gyh20 | 3447 |

# | User | Contrib. |
---|---|---|

1 | cry | 161 |

2 | maomao90 | 160 |

2 | Um_nik | 160 |

4 | awoo | 159 |

5 | atcoder_official | 157 |

6 | -is-this-fft- | 156 |

7 | nor | 155 |

7 | adamant | 155 |

9 | maroonrk | 152 |

10 | Dominater069 | 148 |

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Sep/15/2024 15:54:40 (h2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Just Bumping it . In case someone wanna help .

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

Thanks a lot .

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!!

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.

Thanks bro great explanation

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

Somehow I got the incorrect output for the example case where n = 1337 but I passed all the tests after submitting the code. I'm guessing that the output for the example case is wrong (I got output 651467482 for n = 1337).