Блог пользователя Polar_

[Help] Counting Towers CSES
Автор Polar_, история, 3 года назад, По-английски

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

Теги dp, cses
  • Проголосовать: нравится
  • +2
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Just Bumping it . In case someone wanna help .

→ Ответить
»
3 года назад, # |
  Проголосовать: нравится +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$$$.

→ Ответить
  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Thanks a lot .

    → Ответить
  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 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!!

    → Ответить
    • »
      »
      »
      2 года назад, # ^ |
        Проголосовать: нравится 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.

      → Ответить
  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Thanks bro great explanation

    → Ответить
  • »
    »
    2 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    → Ответить
    • »
      »
      »
      2 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Take a 1 * 2 tower with one single block as a[1] and two blocks as b[1]. Try writing down all the 8 possible towers for n = 2 and visualize the recurrence by drawing a bold line horizontally through the mid of all 8 squares and then segregate a[2] and b[2].

      → Ответить
  • »
    »
    6 недель назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Please suggest me a good material to learn matrix exponentiation!!.

    → Ответить
»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
»
4 месяца назад, # |
  Проголосовать: нравится -10 Проголосовать: не нравится

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

→ Ответить