Alphx's blog

By Alphx, 2 years ago, In English

This is my first Blog. I hope, this blog would be useful for the programmers out there. This blog is an extension to a previous CSES DP editorial written by icecuber. The link to the blog is here. It was a great editorial and which inspired me to complete that with these few leftover problems.

Problems covered in this editorial:Counting Towers, Elevator Rides, Counting Tilings, Counting Numbers.

Feel free to point out mistakes

Counting Towers (2413)

dp[i][p]=Number of ways to fill from 0th position till the ith position.

here p denotes the tile at ith position as following:

dp[i][0] => number of ways for the same such that ith position consist of 2 tiles of width 1 each.
dp[i][1] => number of ways for the same such that ith position consist of 1 tile of width 2.

So,recurrence would be:

recurrence

Time complexity here is O(N) for preprocessing and O(1) for answering each query. So, O(T + N) in total.

Code

Elevator Rides (1653)

its a classical problem of dp with bitmasking. here, I have defined dp as follows:

dp[number of rides][weight on the last elevator used]

So, basically, as number of rides is atmost 20, we can use mask to represent the people we have carried to the top of the building. I have added comments in the code to make it easy to comprehend and understand.

Code

Counting Numbers (2220)

It is a good problem for learning digit DP.

dp state is defined as follows:

dp[ith digit from left][previous digit][leading zeroes][tight]

leading zeroes are the zeroes that come before the first non-zero digit in a number eg:0034, 012.

I have added comments in the code for better understanding. This is a standard digit DP problem.

Code

Counting Tilings (2181)

This is a very interesting classical problem of DP with bitmasking. Here masking is used to represent the blocks currently filled in ith column due to arrangement of blocks on (i-1)th column.

here dp state is defined as follows:

dp[i][mask] = number of ways to fill the grid from ith column to mth column such that the ith column arrangement due to (i-1)th column is represented by mask.

I have added comments in the code for better understanding.

Code

Full text and comments »

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