Please read the new rule regarding the restriction on the use of AI tools. ×

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
  • Vote: I like it
  • +11
  • Vote: I do not like it

| Write comment?
»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In counting towers solution you have written dp[i][p] is Number of ways to fill from ith position till nth position But I think what you mean is number of ways to fill from 0th position to ith position

  • »
    »
    19 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yeah... Thank you for pointing out the mistake...I have corrected it as well as added some explanation (although the formatting may not be very good, advice on that will be highly welcomed).

»
15 months ago, # |
  Vote: I like it +1 Vote: I do not like it

this is kartik arora's, code and explanation If i'm not wrong.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

appreciate this!

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Hey i have a doubt, Is there any way in which we can calculate answer for multiple queries without Recalculating whole dp in Counting Digts problem as Tight depends of the current digit in the number and i tried but can't seem to find one.