damn_me's blog

Given Length and Sum of Digits...
By damn_me, 9 years ago, In English

I was trying solving this problem http://codeforces.com/problemset/problem/489/C. Thinkinh in dp manner, I thought i'll need a table that can tell me the number of i digits that sum to particular j. Then if I want to calculate dp[i][j], then my subproblems will be dp[i-1][sum-j] and so on. However, I am unable to implement this idea.

Please help with this. Also, I coded the brute force way: http://ideone.com/83pdfJ but this gives TLE. Where to optimize in it?

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (9)
| Write comment?
»
9 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Mine code

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

    Yeah, we can do that but I wanted to go for DP manner. Can you please explain that??

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

      I think it would be more difficult to solve this problem with DP.

      → Reply
»
9 years ago, # |
  Vote: I like it +2 Vote: I do not like it

You can solve it by using string. Submission: 8731134.

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

It can be solved more easy with greedy algorithm.

→ Reply
»
9 years ago, # |
← Rev. 3   Vote: I like it +3 Vote: I do not like it 
you can use dp but it is not simple
mindp[i][j] = i digit j sum minimum number witch leading zeros are NOT allowed 
mindp2[i][j] = i digit j sum minimum number witch leading zeros are allowed

now mindp[i][j] can update from mindp2[i-1][j-k] where k = [1,9]
→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Why we are thinking about the leading zeroes? What I thought is for k=1, the only digits are 1 to 9. For k>=0, i'll modify dp[k][j] which denotes k digit with j sum. j<=900 i.e. all possible sum. I'll mark dp[i][1...9] as boolean true or 1. Now, inserting one other for loops which iterate from 0 to 9 (as m) , i'll check if dp[k-1][j-m] is true, if it is, i'll make dp[k][j] as true. Similarly filling whole of the table and then iterating it recursively, I'll get the number. However, this is inefficient complexity wise :P

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

      but i think your approch without considering leading zeroes loos at 100001 because 00001 is false :/

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

You can use dp approach in a tabular form but only till 4 test cases will be passed but in the 5 test case the number given is 100 digit long which by no way can be stored in the table. Anyways this solution csn be used for dp tabular solution-http://codeforces.com/contest/489/submission/23355950

→ Reply