Your approach fails for a lot of test cases, So there seems to be some fundamental flow in your approach or your implementation.
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
can u give any test case where it is giving wrong answer
Time complexity of your code is O(N) which is too much to pass under 1 sec.
N = 1603, correct answer = 2332/8015, your answer 1061/3206.
That was error.Thanks!
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
Note that number of states are lot less than theoretical bound. The first time you use the required digit, the last bit turns 1 and stays 1 forever, so there is a cut of 2, like wise for tight also.
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
i am not getting the approachā¦ please explain it a bit.???
For N = 99999999999995030. Your answer is 168856449015893429/-999999999999950300, which is wrong.
1 Like
thanx, I was using lld instead of llu
Can someone check my submission, please? 
http://www.codechef.com/viewsolution/6340700 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.
its very strange, I submitted your solution using g++ 4.3.2. It passed.
Yes, thanks, it passed. Can you tell me, whatās the difference amid the compilers?
Could someone help me out with debugging my solution http://www.codechef.com/viewsolution/7239838 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;
Read about reference variables.
Oh Sorry! I didnnāt see its &ret = dp[i][lt][st][found];