ANUBGC - Editorial

editorial
, , ,
1

PROBLEM LINK:

Practice
Contest

Author: Anudeep Nekkanti
Tester: Gerald Agapov
Editorialist: Praveen Dhinwa

DIFFICULTY:

EASY MEDIUM

PREREQUISITES:

dynamic programming

PROBLEM:

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.

SIMPLIFICATION.

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[0] + … + ans[9]) / (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.

QUICK EXPLANATION

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)).

EXPLANATION

If you are not comfortable with digit dp, have a look at this blog post on codeforces by niklasb. It is really a great tutorial on digit dp.

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.

Base Case:
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.

Transitions:
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.

Complexity:
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).

AUTHOR’S, TESTER’S AND EDITORIALIST’s SOLUTIONS:

Author’s solution Iterative
Author’s solution Recursive
Tester’s solution
Editorialists’s solution

15 Likes
2

@dpraveen:Please fix the solution links. It’s being redirected back to the same page

1 Like
3

Why does the tester’s solution gives wrong answer?

Link:- http://www.codechef.com/viewsolution/3923245

2 Likes
4

@anudeep


i was not able to come with a dynamic programming idea so, i tried to do it this way can you check it whats wrong with this . please

1 Like
5

Can you explain your idea, so that it will be easy to understand.

6

i thought of this way
first i thought of calculating number of numbers which contains 1,2,3,4…and zero

i did to do this by calculating complementing of what i actually need
i count the number of numbers below N which actually does not contain 1,2,3,… in it and then subtract it from the N and add it to the count

7

i did this in following manner suppose
N=53
i need to calculate the number <=N containing 1 in it so i can fixed any of this number at the first place.
(0,2,3,4) total 4 numbers at first position so (4)X9 ways
then i fixed 5 at the first place 1X(3) so total ways are 36+3=39(including 0) so total ways are 38 and the actual numbers are (53-38)=15.

8

It seems that Gennady’s solution does not use DP and he seems to have used something related to this answer on StackOverflow. (See first answer)

4 Likes
9

Hey, this approach has been explained here - stackoverflow.com/questions/11156876/given-a-number-n-find-out-how-many-numbers-have-digit-2-in-the-range-0-n

10

@wittyceaser
can you explain this appraoch here.
and also can you tell me whats wrong with my approach.

11

can you have a look over my code.

12

Check out the solution that I’ve referenced above properly, you’ll get a fair enough idea.

2 Likes
13

http://www.codechef.com/viewsolution/3922153
My this solution was having an overflow.Can anyone tell me why?

14

Hello,
Find recursion here http://ideone.com/WBfBdi
Or http://www.codechef.com/viewsolution/3923634

Example:

             //split range from to maximum long containing 9 at the end
             count 9 in range 0--245  = (count 9 in range 0--239) //use recursion as given below
`                                     + (count 9 in range 239--245)  //count manually

             (count 9 in range 0--239) =`(count 9 in range 0--23 * 10) 
`                                    `+  (total numbers in range 0--23) 
                                      -  (count 9 in range 0--23)

             //split range from to maximum long containing 9 at the end
             count 9 in range 0--23  = (count 9 in range 0--19) //use recursion as given below
`                                     + (count 9 in range 19--23)  //count manually

             (count 9 in range 0--19) = (count 9 in range 0--1 * 10) 
`                                    `+  (total numbers in range 0--1) 
                                      -  (count 9 in range 0--1)
             (count 9 in range 0--1)  = 0
2 Likes
15

Thank you for the wonderful editorial :smiley:

3 Likes
16

@snapshot: The wrong solution of tester was uploaded. You can see that in the solution, gcd is always 1 and hence this is wrong. If you calculate correct gcd, then the solution will work. I am updating the correct solution. Thank you :slight_smile:

17

@kuruma: I am glad you liked the editorial :slight_smile:

18

@snapshot: That was the starting time of uploading the editorial, Now all the links are working. If you find some dead or not working link, please write comment a about that. Thank you.

19

why was mod used in your program?

20

can anyone pls check why my soln giving WA
http://www.codechef.com/viewsolution/3923994