PROBLEM LINKS
DIFFICULTY
MEDIUM
EXPLANATION
The problem can be solved using Dynamic Programming. We try and form the number starting at the most significant digit and moving towards the least significant digit. We can compute the answer as S(B) - S(A-1), where S(X) is the sum of the slopes of all numbers <= X.
The state can be represented as :
F(k, d1, d2, eq) where
k : The current digit to be filled
d1 : The second last digit
d2 : The last digit
eq : Boolean parameter which is 1 if the partial number formed is equal to the corresponding digits in X, 0 otherwise. It means that we have not placed a smaller digit yet and thus restricts the possible digits we can place next, in order that we do not exceed X.
We try to place all possible digits d3 at index k. If d2 > d1 and d2 > d3, it means that d2 is a maxima and we add to the answer the total numbers which can be formed there onwards. Similarly for a minima.
Finally, we can optimize by noting that the actual value of d1 is not needed. It suffices to know if d1 <= d2 or d1 = d2 or d1 > d2.