Editorial for New Year's '18 P4 - 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.

Author: Kirito

For $10\%$ ~10\%~ of points, we can iterate the through all integers in the range $[L,R]$ ~[L,R]~, and check the number of distinct $\operatorname S(x)$ ~\operatorname S(x)~ values.

Time Complexity: $\mathcal O((R-L)\log_{10}R)$ ~\mathcal O((R-L)\log_{10}R)~

For the remaining $90\%$ ~90\%~ of points, we can solve the problem with dynamic programming. Firstly, observe that the values of $\operatorname S(x)$ ~\operatorname S(x)~ are in the range $[1,162]$ ~[1,162]~. Let $\operatorname f(x,y)$ ~\operatorname f(x,y)~ be the number of numbers less than or equal to $x$ ~x~ such that the sum of their digits is equal to $y$ ~y~. The value of $\operatorname f(x,y)$ ~\operatorname f(x,y)~ can be determined with dynamic programming, more specifically, digit dynamic programming. Let $dp[digit][sum]$ ~dp[digit][sum]~ be the number of ways to obtain a sum of $sum$ ~sum~ with $digit$ ~digit~ digits remaining, while still being less than or equal to $x$ ~x~. Thus our DP recurrence is:

$\displaystyle dp[sum][digit] = \sum_{i=0}^9 dp[sum-i][digit-1]$

The answer is thus the number of non-zero values of $\operatorname f(R,y) - \operatorname f(L-1,y)$ , for each value of $y$ ~y~ in the range $[1,162]$ ~[1,162]~.

Time Complexity: $\mathcal O(\log R)$ ~\mathcal O(\log R)~ with a large constant factor

Comments

9

InfernoApeZ commented on Jan. 9, 2018, 2:19 a.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.