Check out the solution that I’ve referenced above properly, you’ll get a fair enough idea.
Thank you for the wonderful editorial
@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
@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.
why was mod used in your program?
Your approach fails for a lot of test cases, So there seems to be some fundamental flow in your approach or your implementation.
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!
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.
i am not getting the approach… please explain it a bit.???
For N = 99999999999995030. Your answer is 168856449015893429/-999999999999950300, which is wrong.
thanx, I was using lld instead of llu
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?
Read about reference variables.
Oh Sorry! I didnn’t see its &ret = dp[i][lt][st][found];