ANUBGC - Editorial

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

18 Likes

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

1 Like

Why does the tester’s solution gives wrong answer?

Link:- CodeChef: Practical coding for everyone

2 Likes

@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

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

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

Hello,
Find recursion here WBfBdi - Online Java Compiler & Debugging Tool - Ideone.com
Or CodeChef: Practical coding for everyone

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

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

please someone explain why it is giving TLE ,i used the similar type of algorithm

answer will be reduced form of (N + sum of no. of distinct digits in numbers from 10 to N)/N*10;

ANSWER for N<=9 WILL BE DIRECTLY 1/10

why TLE?
http://www.codechef.com/viewsolution/3923010

Overall time complexity is 80 * log10(N) for finding each digit D right ? Then when finding ans[0] + ans[1]… upto ans[9] it will take 80 * 10 * log10(N) which is more than 13000. There are 10000 test cases , so won’t this be a tight complexity ? A more general question is that , on a problem which runs on cube cluster , what should be the number of operations which can be carried out in 1 sec , for a general overview ? I assume it to be like 10^8 per sec , so under the TL of 2 s, this complexity will pass.

1 Like

hey! I cross checked a number of test cases with a correct submission, but mine’s giving wrong answer!
It’d be very nice of you to check my solution here:link text

Can someone check my submission, please? :slight_smile: CodeChef: Practical coding for everyone I’m trying to implement that algorithm from given niklasb link, but it doesn’t work out for me. I’m getting TLE, but, correct me if I’m wrong, the algorithm does at most 10000 * 1600 = 16M operations, which should pass the test cases.

Could someone help me out with debugging my solution CodeChef: Practical coding for everyone which is giving WA result?

I have tried a lot of test cases by taking some tricky test cases as well as large random values and compared the result with the output of an accepted solution, but I am unable to find a case that gives different answers. :frowning:

My approach is as follows:

→ I am counting the number of numbers in the range [1,N] which don’t have a particular digit in their decimal representation. I am storing this value for each of 0,1,2…9 in the array “nos_not_containing[]”. For doing this I am following this method :
Say we have N=578 and we are counting nos_not_containing[3] for this N:
1.Let the first digit be 0,1,2,4, then other 2nd digit can be anything except 3:
499-1(for 000 case)=323
2.Let the first digit be 5(set at its max value); and second be 0,1,2,4,5,6, then the third digit can be anything except 3:
6*9=54
3.Let the first digit be 5(set at its max. value) and the second digit be 7(set at its max value), then third can vary only upto 8(except 3 again):
8

->The final probability = 1- (sum of all values in nos_not_containing[] from 0 to 9)/(10*n)

Could someone please give me any test case where my solution fails or point out any potential error in my code?

In the recursive solution of the author …
He is not modifying the dp in the solve function.
Shouldn’t it be
return dp[i][lt][st][found] = ret ;
instead of
return ret;

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

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

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.

Hey, this approach has been explained here - algorithm - Given a number n, find out how many numbers have digit 2 in the range 0...n - Stack Overflow

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

can you have a look over my code.