simp_pro's blog

Good Digit DP problem
By simp_pro, history, 2 years ago, In English

You are given N. Find number of pairs of integers x, y such that

1 <= x < y <= N and sumOfDigits(x) > sumOfDigits(y)

Constraints:

N <= 10^100 and is given as a string.

Output answer modulo 1e9+7

I don't remember the sign of inequality properly, it might be sumOfDigits(x) < sumOfDigits(y). I read about digit DP to solve this but I cannot find any approach.

How to solve this?

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

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

keep two tight high (one for x, one for y).

dp states would be : index,thigh1,thigh2,sumx,sumy,flag.

sumx represents sum of digits of x and sumy represents sum of digits of y.

flag is a boolean variable which tells whether at the first place of distinction between digits of x and y , digit of x was smaller or not.

→ Reply