Nourin_Eka's blog

By Nourin_Eka, 8 years ago, In English

Any useful link to learn the idea o Digit DP?

To solve problems like those:

http://www.lightoj.com/volume_showproblem.php?problem=1205 http://www.lightoj.com/volume_showproblem.php?problem=1068 http://www.lightoj.com/volume_showproblem.php?problem=1122

Or any idea about solving this kinds of problems...

 
 
 
 
  • Vote: I like it
  • -1
  • Vote: I do not like it

»
8 years ago, # |
Rev. 2   Vote: I like it +2 Vote: I do not like it

LOJ - 1068

Let's generalize the problem. Given a number (1 <=) N (<= INT_MAX). Find how many numbers in the interval [0, N] are divisible by (1 <) K (< 1e4).

So you've to make all the numbers from 0 to N, how to do it? In each state, suppose you have made a number. Now try to place digits (0 — 9) after it and check if the new number is smaller or equal to N. Say, N = 1652 and current number = 165. So the valid numbers are :

        165 * 10 + 0 = 1650
        165 * 10 + 1 = 1651
        165 * 10 + 2 = 1652

These are the new numbers we can make. But handling integers will cause MLE. So you've to treat them as string. Again passing whole string would be stupid too. So let's optimize it. In current state, what you really need to know is how to make a valid new number? That is, which digits you can place (or till which digit you can place starting from 0). Now, in any previous state, if you have placed a smaller digit corresponding to N's digit, then current number is absolutely smaller then N and whatever you place after this number will be smaller then N.

        N = 1652
        current number = 155
        So you can place any digit after 155 to make a valid number

Now, if you haven't placed any smaller digit corresponding to N's digit, then you can from 0 to N's corresponding digit.

        N = 1652
        current number = 165
        So you can place 0, 1 and 2 after 155 to make a valid number

And of course this process would continue till length length (intToString (N)). So one DP state is [pos], another is [preSmall]. One more state is left (divisibility).

Now, checking for divisibility. Following code-segment would do the work :

DP (int pos, int moded, bool preSmall) {
        moded *= 10;
        for (....) DP (pos + 1, (moded + digit) % K, ...);
}

After making a number, if moded is 0, then the number is divisible by K.

The value of moded will be [0,K). So the total complexity will be len * K * 2. And maximum value of len will be at most 10.

This is the solution of the generalized problem. To get the expected result, simply do solve (B) - solve (A - 1).

Thanks

  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thank You :)

  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    So far I could guess your DP (int pos, int moded, bool preSmall) gives the number of integers divisible by k, not whose sum of digits also divisible by k. LOJ 1068 requires that. And if I my guess is correct then it can be calculated mathematically, n/k gives us the number of integers less than or equal to n divisible by k. DP(int pos, int moded, int preSmall, int sum) I think if we design the DP like this one, it may answer that question, but complexity grows 10*1e4*2*83 which is neither time nor memory efficient. How can we optimize it further.

    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      if K > 100 there is no solution so answer is 0 :)

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        actually if k > 74 then there is no solution.since number of digit is 9 and 2 * (8 * 9) = 74.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it -6 Vote: I do not like it

    Helped me alot. Thank You :)

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

This stack overflow link is also very useful : LINK

»
4 years ago, # |
Rev. 3   Vote: I like it -34 Vote: I do not like it

I am a newbie to Dp. Now i am trying to solve some problem related to digit dp. link: http://www.lightoj.com/volume_showproblem.php?problem=1068

solution: https://pastebin.com/4R9Q4BYv

I was trying to solve the above metioned problem but got stucked.

Any help would be appriciated.

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

    Please, remove your code and paste it to any code sharing site like ideone.com, pastebin.com then share the code link.

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

I am a newbie to Dp. Now i am trying to solve some problem related to digit dp. link: http://www.lightoj.com/volume_showproblem.php?problem=1068

solution: https://pastebin.com/4R9Q4BYv

I was trying to solve the above metioned problem but got stucked.

Any help would be appriciated.