determinism's blog

Error in My Solution of 507D
By determinism, 9 years ago, In English

Problem: D. The Maths Lecture

My solution:

I have 3 arrays:

  • base: It contains base values of digits modulo k.
  • dp: dp[i][j] is the number of suffixes of length i which equals j modulo k.

dp[0][0] = 1

dp[i+1][(j+base[i]*d)%k] += dp[i][j] where (1 <= i < n) & (0 <= j < k) & ((i == n-1 ? 1 : 0) <= d <= 9)

  • dp2: dp2[i][j] is the number of prefixes of length i which equals j modulo k.

dp2[0][0] = 1

dp2[i+1][(j+base[n-1-i]*d)%k] += dp2[i][j] where (1 <= i < n) & (0 <= j < k) & ((i == 0 ? 1 : 0) <= d <= 9)

res equals (dp[n][0] + dp[n-1][0] * (dp2[1][1] + dp2[1][2] + ... + dp2[1][k-1]) + ... + dp[1][0] * (dp2[n-1][1] + ...)) % m

Source Code

This way seemed correct to me, but it outputs 835 instead of 590 for the 3rd test case. What's my mistake?

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

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

you are counting same values twice or more.

for 5 3 1103

33333 — u count it 5 times :)

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    I think that I count 33333 only in dp[n][0]. I don't count it in others because prefixes are also 0 modulo 3. Can you elaborate it?

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

why would you need a prefix i didnt need it... there is absolutely no reason to use dp2 it would just get more complicated

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

    Can you explain your solution?

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

      Although I miserably failed to solve this problem during the contest, at a first glance it seemed like a very classic DP question (it actually is). The problem I think you're having to understand as to why the solution provided in the editorial works is because you're thinking that you are "constructing" the numbers from left to right. When I believe they happen to be constructing it from right to left. Basically, if they have to form a 5-number digit n=5 (XXXXX) with a suffix that is divisible by K = 100. Once they reach a given a position where the current number is divisible by 100 ie : (XX100, XX200, XX300, XX400, ..., XX900), they just need to know how many numbers can fit in the "empty buckets" (XX).

      I hope you understand why I'm trying to say.

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

      well i defined dp[i][j] as the number of numbers with i digits which have j as their modulo with k which AND THEY DON'T HAVE ANY SUFFIXES WHICH HAS ZERO MODULO thats the only trick and you should watch out that we should count numbers like 9000000 because 0 is included in the thing we have before so we should add that and for every dp[i][0] we have dp[i][0] * (10 ^ (n — i — somenumbecalculateityourselfmymindisbusy) * 9) except dp[n][0] (it has alotta special cases if i didn't include them please comment about it)

      → Reply