### Death_Scythe's blog

By Death_Scythe, history, 9 years ago,

Hello all! I found this problem on CodeChef: http://www.codechef.com/problems/PRYS09

I honestly don't know where to start. The brute force approach obviously won't work. Also, there are no solutions and editorials available probably because this is an old contest problem and remained unnoticed by the users. Please help!

Thanks!

• +3

| Write comment?
 » 9 years ago, # |   0 I think it can be done with dynamic programming (to be able to count f (x) = the number of numbers up to x with the desired property, so the answer is f (R) — f (L-1)). The state is how many digits you've placed, whether or not you have already gone below x on some digit, and the current sum of cubes of digits mod m. Then you try each possible digit and get a new state for each valid digit.
•  » » 9 years ago, # ^ |   0 Thanks for the reply mkirsche! I am not very good at DP problems so I am not sure how to start writing the code. If you don't mind, can you please write a pseudocode? Thanks a lot! :)
•  » » 9 years ago, # ^ |   0 I tried . Got tle'd CODE
 » 9 years ago, # | ← Rev. 2 →   +4 Calculate F(l, m, r) as number of numbers with length not more than l, such that sum of the cubes of their digits equals to r by modulo m. Then each query can be processed by O(sum_of_digits).Lets di be the i-th digit of query number n and l its length. Iterate by prefixes, for each d < di adding to answer F(l - i - 1, m,  - (sum_of_cubes_on_prefixi - 1 + di3)%m).