spirited_away_'s blog

By spirited_away_, history, 9 months ago,

How to handle 0's in this problem. Like when you have input like 230005450569. When there is no 0's the answer will be 2^n-1 when C is infinity. Now for C we will count how many numbers we have to subtract from answer which are >= length of C. But how to handle 0's in this case like sample input above.

• +4

 » 9 months ago, # |   0 Why don’t you just count the answer itself with DP? The length of possible number is maximum 10, so for every position you’d only need to check 10 possible numbers for validity.
•  » » 9 months ago, # ^ |   0 How can we do that. When we look for C length then what about rest of digits. How we will handle them . And specially zeros.Since 12 can be answer but 00 can't be.Can you describe your approach in more detail.
•  » » » 9 months ago, # ^ | ← Rev. 2 →   0 $a_i$ – the amount of splits considering only the first $i$ digits.$a_0 = 1$$a_i = \sum_{j=\max(0, i-10)}^{i-1} a_j$, if number formed by digits $[j..i)$ is valid (has no leading zeroes and is $\leq C$)
•  » » » » 9 months ago, # ^ |   0 if the number formed by digits[j..i) is not valid then a[i] = 0. is it correct?
•  » » » » » 9 months ago, # ^ |   0 I think you meant $a_j$, but yes, for that it’s enough to check first digit. Don’t forget that you still need to compare the whole number as well though.
•  » » » » » » 9 months ago, # ^ | ← Rev. 4 →   0 yes, sorry. if j to i-1 is not valid then a[ j ] = 0. and by max(0,i-10) you mean max(0,i-C). Please correct me if wrong.
•  » » » » » » » 9 months ago, # ^ |   0 C is not the boundary of the length of a number. It is a boundary of a number. 10 is coming from the fact that the maximum allowed value of C has 10 digits.
•  » » » » » » » » 9 months ago, # ^ |   0 Ok, thanks i understood it.
 » 9 months ago, # | ← Rev. 2 →   0 can you provide problem link?
 » 9 months ago, # |   +28 I don't trust authors who use Latex but still manage to write $<=$ instead of $\le$.