Though the editorial mentions a reverse iterative approach to solve the problem with O(N) time complexity, I used binary search to solve the problem. Even after multiple rechecks, I am unable to find the bug in my code that is causing Case 58 to result WA. Hence can anyone please point out the bug in my solution ?
1 Like
A large no of soln failed on Test Case 58. It’s mainly due to precision error with doubles. What I think is this TC was designed so that soln which have incorrect condition to print -1 should fail.
Your soln AC with corrections - http://codeforces.com/contest/1011/submission/40856287
Cheers.
1 Like
Although @aryanc403 has solved your query, it’s just another way of doing binary search on doubles which could make your code a little smaller…instead of checking with epsilon you increment or decrement low and high by given precision.
Binary search will terminate when it finds an answer and answer will definitely be of that precision since we have incremented value by that. Have a look at code.
May be it’s obvious but i found this worth mentioning here if it helps 
Ask if something is not clear
My sol
1 Like
I also faced same problem,this is happened due to precision loss,for my case my o/p was -1 instead of 1000000000.0000000000.
this is because i don’t add the error of 10^-6 for more safe you can set the lo=1e9+1 during binary search,i see many people do it only with maths.
link to my soln with binary search : http://codeforces.com/contest/1011/submission/40814822
i think this will help
happy coding:)
1 Like