undefined_error_'s blog

Fast Bit Calculations
By undefined_error_, history, 5 years ago, In English

I am trying to solve the problem for a while but couldn't come up an idea. It would be great if someone can help me to solve the problem. Details explanation would be better. Problem Link: https://vjudge.net/problem/LightOJ-1032

Thanks a lot :) sorry for my poor English. :)

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

»
5 years ago, # |
  Vote: I like it +5 Vote: I do not like it

use digit dp. the states will be the current digit position, a flag for number already smaller or not, and the previously used digit.

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

    Thanks man, can you explain a bit in details. I am not familiar with digit dp. :)

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 3   Vote: I like it +14 Vote: I do not like it

      It's quite hard explaining that problem if you're not familiar with digit dp, so I'm showing a much simpler one first.

      The problem may seem stupid in a sense, it is : given n, find number of positive integers <= n. Ya, very hard. Let's try it with digit dp.

      Say our n = 110. We try to make a number from the most significant decimal place. Initially we assume our number is like *** with no digits determined yet. We say number of ints <= n from this state is dp[2].

      Now we can put 0 or 1 to at the leftmost digit to satisfy <= n condition. We can calculate dp[2] = dp[1] + dp[1].

      But wait, if we put a 0, then next time we can put anything from 0 to 9, but putting 1 means we can only put 0 or 1 at the next time. So we need another state, that is something like "is our number already smaller than n?".

      so initially dp[2][0] means we are at the 2nd place with our number equaling n so far, thus we can't put anything greater than the digit at that place of n. then we can calculate it like dp[2][0] = dp[1][0] (when putting 1) + dp[1][1] (when putting 0) and then,

      $$$dp[1][0] = dp[0][1]$$$ (putting 0) $$$+ dp[0][0]$$$ (putting 1)

      $$$dp[1][1] = dp[0][1]$$$ (putting 0) $$$+ dp[0][1]$$$ (putting 1) $$$+ .... + dp[0][1]$$$ (putting 9)

      It goes like that.

      So $$$dp[i][0/1]$$$ = number of integers $$$<= n$$$ when we are at the ith position (0/1 suggesting already smaller or not)

      $$$dp[i][0] = \sum_{d = 0}^{n_i}dp[i - 1][d < n_i]$$$

      $$$dp[i][1] = \sum_{d = 0}^{9}dp[i - 1][1]$$$

      as for base cases, $$$dp[-1][x] = 1$$$

      This is the essence of digit dp, you only care about what digits you put and how much that contributes to the result.

      Now for that problem, notice you only need to know what you put as previous digit. That way you can add to your contribution when you put two consecutive 1's. It looks like this, $$$dp[i][0/1][prev]$$$ = ans with i digits, with previous digit being prev.

      I'll just show one case,

      $$$dp[i][0/1][1] = dp[i - 1][1][0]$$$ (putting 0) $$$+$$$ (if you can put 1) $$$dp[i - 1][0/1][1]$$$ + (number of integers $$$<= n$$$ from $$$i - 1$$$ th pos :)

      Not so sure if this helped, I'm sure you will also find a lot of other good tutorials online about digit dp, do check those out.

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

      Here's a really good blog on Digit-DP

      → Reply