## Editorial for The Polar Express

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

Authors: Kirito

For of points, we can iterate the through all integers in the range , and check the number of distinct values.

Time Complexity: .

For the remaining of points, we can solve the problem with dynamic programming. Firstly, observe that the values of are in the range . Let be the number of numbers less than or equal to such that the sum of their digits is equal to . The value of can be determined with dynamic programming, more specifically, digit dynamic programming. Let be the number of ways to obtain a sum of with digits remaining, while still being less than or equal to . Thus our DP recurrence is:

The answer is thus the number of non-zero values of , for each value of in the range .

Time Complexity: , with a large constant factor.

• InfernoApeZ  commented on Jan. 8, 2018, 9:19 p.m.

I am slightly confused. I'm pretty sure that there are several solutions to this problem (including mine) that are incorrect and should WA. In my solution, I find the minimum sum of the digits and the maximum sum of the digits possible between the numbers L and R. Then, I assume all the sums in between the min and the max can be reachable. Therefore the answer would be the max-min+1. I am really surprised that this solution gives AC as I can think of many situations where this code would WA such as 99 and 100, 3000 and 10000, 150 and 200, etc... Should the test cases be updated or something? lol.