You are given an integer N. You select a digit d randomly from 0 to 9. You also select a number randomly from 1 to N. You win if decimal representation of the selected number contains digit d. Find out probability that you will win.
For each digit d, let us suppose your are able to find out ans[d] : the number of numbers from 1 to N
whose decimal representation contains d. Then final answer of our problem will be (ans + … + ans) / (10 * N).
Now you are supposed to output this number in irreducible fraction format. A fraction p/q is called irreducible if gcd(p, q) = 1. So you have to calculate numerator and denominator, Then divide both of them by their greatest common divisor, resulting fraction will be in irreducible format.
Hence, our main problem is following: for a given digit d, we need to find out number of numbers from 1 to N containing d in their decimal representation.
We can do a digit dp having state (current index, whether the currently constructed number of i digits is equal or less than the number formed by first i digits of N, whether the digit d has appeared in the constructed number or not, is the constructed number consists only of zeros. (i.e. the actual number is not started yet)).
Conceptually you can view digit dp as construction/generation of numbers from most significant digit to least significant digit. The main idea is that
you dont need to know the entire constructed number but you can do your operations by simply knowing a few properties about the constructed number.
eg. in our case, we need to know whether the number contains d or not.
Whenever in the editorial we talk about first i digits, by that we mean the most significant first i digits.
Let dp[i][tight][found][started] denote the number of numbers whose first i digit have been considered and tight denotes whether the currently constructed number is equal or less than number formed by first i digits of N.
If tight is true, then it means that currently constructed number is equal to number constrcuted by first i digits in decimal representation of N.
If tight is false, then it means that currently constructed number is less than number constrcuted by first i digits in decimal representation of N.
found denotes whether we have found the digit d in the number constructed up to now,
started denotes whether the number is actually started or it is just simply a series of zeros only (ie. Whether or not some non-zero digit in the number has appeared).
We can do a forward dp in following way. If you are not comforable with idea of forward dp, you are recommended to view this amazing tutorial on topcoder.
If i = number of digits in decimal representation of N, started = true and found = true, then answer = 1.
Note that by our construction, we make sure that the constructed number of length i is always less or equal to some first i digits of N.
Hence the final constructed number <= N. Note that in this case, the number will always be >= 1, because otherwise started would have been false.
We can consider following options for filling (i+1) th digit when we have already filled the first i digits.
If tight is true, then it means that our constructed number is still equal to number formed by first i digits of N. Then we can try our current possible digit value from 0 to (i+1) th digit of N. If we try the digit more than (i+1) th digit, then the constructed number will become greater
than number formed by first i digits of N, which will violate the property that our constructed number should be <= N.
After filling out this state, we will go to i + 1, hence new_i = i + 1.
If we take our current digit i to be strictly less than dig[i], then our new_tight will be false.
If we have already digit d in our current number (i.e. found is true), then new_found is also going to be true.
But if found is false, then we have to check whether the current digit is equal to d or not, if it is equal to d, then digit d has occurred in our
constructed number, hence we will set the new_found = true.
Similarly if our started is true, then new_started is going to remain true. If started is false, then we will check whether the current digit value we are considering is non-zero or not, if it is non-zero, then we will set the new_started = true
If tight is false, then it means that number constructed from first i - 1 digits has become less than number constructed from the first i - 1 digit of N, So it means that our number can never exceed N, so we can chose the any digit from 0 to 9 and do the transitions in the same way as explained in the previous paragraph.
For representing N in its decimal value, we will add an extra zero to its beginning. This will felicitate our purpose of getting our answers nicely.
For finding out answer, we need to call dp(0, 1, 0, 0), because initially i = 0, tight = 1, because our constructed number is 0 and N is first digit is also 0 (this is the exact reason of adding one extra 0 digit in the beginning of decimal notation of N). Both found and started are going to remain false.
If you did not get what is mentioned above clearly, you are recommended to have look at editorialist’s solution and try working out a simple
example by hand.
Number of States:
i can be between 0 and (number of digits in decimal notation of N) inclusive. i.e. 0 <= i <= log10(N).
tight can be between 0 and 1 inclusive. i.e. 0 <= tight <= 1.
found can be between 0 and 1 inclusive. i.e. 0 <= found <= 1.
started can be between 0 and 1 inclusive. i.e. 0 <= started <= 1.
Hence number of states = log10(N) * 2 * 2* 2 = 8 log10(N).
Number of transitions:
10 per state (as we are iterating over digits from 0 to 9).
Hence overall time complexity: Number of states * Number of transitions = 8 * log10(N) * 10 = 80 log10(N).