EugeneJudo's blog

How to get the right DP solution?
By EugeneJudo, history, 3 years ago, In English

I worked through https://cses.fi/problemset/task/2413/, but i'm not too happy with my implementation: https://cses.fi/paste/a16f2727089e9e76291e5a/

It's very complicated, as I went with a route I saw would work, but knew would be hard to implement. Every integer represents one of the 20 possible row states, and dp figures out in the next row how many of type X appear based on the sum of the states that allow for type X to appear next. Looking at others solutions, no such enumeration is necessary, but I can't really understand why the alternative method works. Could someone explain the proper approach here?

  • Vote: I like it
  • +8
  • Vote: I do not like it

»
3 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I think the following approach is correct:

Let $$$f(n, 0)$$$ be the number of towers of height $$$n$$$ such that on the highest floor both columns are occupied by the same block; and $$$f(n, 1)$$$ the number of towers of height $$$n$$$ such that on the highest floor the columns are occupied by different blocks.

Then, from the state $$${n, 0}$$$ you can:

  • add a new block that covers both columns on top of the highest floor, leading to the state $$${n+1, 0}$$$.

  • extend the highest block to a new floor, leading to the state $$${n+1,0}$$$ too.

  • add one block for each column on top go the highest floor, leading to the state $$${n+1, 1}$$$.

And from the state $$${n, 1}$$$ you can:

  • add a new block that covers both columns on top of the highest floor, leading to the state $$${n+1, 0}$$$.

  • add one block for each column on top go the highest floor, leading to the state $$${n+1, 1}$$$.

I hope you can get the final transition recurrence formula. You should have no troubles once you understood everything I said above.

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

    Very close, but not quite. For the state $$$n, 1$$$, you must account for doing the following for the next row:

    • Old, Old
    • Old, New
    • New, Old
    • New, New

    for the state $$$n+1, 1$$$.

    The transitions are as follows:

    • $$$f(n, 0) = 2f(n+1,0) + f(n+1,1)$$$
    • $$$f(n, 1) = f(n+1,1) + 4f(n+1,0)$$$

    Implementation note: It's easier to use $$$dp_{i,0}, dp_{i,1}$$$ to be the answers for $$$n = i$$$, transition from $$$n$$$ to $$$n + 1$$$ with the formulas above. And if you sort the input, you can even solve it in $$$O(t)$$$ memory.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Oh true. I was careless for the transitions going out from the state $$$n,1$$$.

      → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Thanks for the elaboration, the old/new phrasing made it very clear what's going on. I believe the states are mixed up in the second formula, since the 4 applies to different blocks at the top level. Also making n increase instead of decrease yields:

      • $$$f(n+1,0) = 2f(n,0) + f(n,1)$$$
      • $$$f(n+1,1) = f(n,0) + 4f(n,1)$$$
      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        Yes, I just wanted to use the same notation that aniervs used, because most readers will probably read that first.

        → Reply