Codeforces Round #714 Add One - DP

Solution:

Solution 1:

Define $dp_i$ as: after m operations, the length of result change from 1.

So of course for $0\leq{i}\leq{8}$, $dp_i=1$.

For $i\geq{9}$, we can plus 9 first. Then the 1 from beginning changed to 10. Now the question turn into:

1. After $i-9$ operations, the length of result which change from the 1 in the first position.
2. After $i-9$ operations, the length of result which change from the 0 in the second position.

And refer to the definition of $dp$, the answer of first question is $dp_{i-9}$.

And for the 0 in the second position. We can plus 10, so that we can get 10 again. And the number of operations is $i-9-10$ for the number 1. And the length is $dp_{i-9-10}$

Keep doing this until the remaining number of operations does not exceed 10. And we can get the formula below:

$$dp_i=1+dp_{i-9}+dp_{i-9-10}+dp_{i-9-10-10}+...$$

Now we just need calculate the prefix sum for every 10 operations. So that we can get the sum of $dp_{i-9-x\times{10}}$ directly.

Solution 2:

On solution 1. When we plus 10 for the 0 in the second position. But actually, we can do one operation, and change the 0 to 1. Then we can get $dp_i=dp_{i-9}+dp_{i-10}$. Much more easier.

Code