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
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
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? 
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. 
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.
Check out the solution that I’ve referenced above properly, you’ll get a fair enough idea.
2 Likes
Thank you for the wonderful editorial 
3 Likes
@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 