Hi, Codeforces!
I have a question that most of you might find it very easy, about problem 489C - Given Length and Sum of Digits...
I'm actually still a newbie at solving Div2-C problems, since then I would be very glad if someone of you can help me with my question.
The question is: How does the DP approach of this problem differ than the greedy one written in problem's tutorial?
Thanks all, thanks in advance for this great community funded by your contributions!
Good luck with today's round btw ;)
The DP approach applicable here is commonly known as Digit DP. Here, you consider the number as a decimal string and add digit after digit for each index and eventually at index m check whether current summation of digits equals to s or not. Hence the states would be index and currentSum. For maximizing, start adding numbers from 9 to 0 and for minimizing do the opposite with a check that you don't add leading zeros. Finally print the DP solution to get the desired output.
Here are some good Digit DP problems.