Блог пользователя damn_me

Автор damn_me, 10 лет назад, По-английски

I was trying solving this problem http://mirror.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?

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
10 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
»
10 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

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

»
10 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

It can be solved more easy with greedy algorithm.

»
10 лет назад, # |
Rev. 3   Проголосовать: нравится +3 Проголосовать: не нравится
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]
  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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://mirror.codeforces.com/contest/489/submission/23355950