Death_Scythe's blog

A problem related to sum of cube of the digits
By Death_Scythe, history, 9 years ago, In English

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!

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

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

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.

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

    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! :)

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

    I tried . Got tle'd CODE

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

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).

→ Reply