spirited_away_'s blog

By spirited_away_, history, 7 weeks 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

 » 7 weeks 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.
•  » » 7 weeks 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.
•  » » » 7 weeks 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$)
•  » » » » 7 weeks ago, # ^ |   0 if the number formed by digits[j..i) is not valid then a[i] = 0. is it correct?
•  » » » » » 7 weeks 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.
•  » » » » » » 7 weeks 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.
•  » » » » » » » 7 weeks 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.
•  » » » » » » » » 7 weeks ago, # ^ |   0 Ok, thanks i understood it.
 » 7 weeks ago, # | ← Rev. 2 →   0 can you provide problem link?
 » 7 weeks ago, # |   +28 I don't trust authors who use Latex but still manage to write $<=$ instead of $\le$.