Can someone please point out what is wrong in my solution. It is giving WA for 3 testcases. I have used a simple binary search with a check function. The bounds are 0 and 2e18 and I am including Ci + D as shoot time also. Please help me out ! Thank you !
1 Like
We are binary searching over double here, so it is always a good idea to either run binary search for a fixed number of iterations(say 100) and change the condition as while(high -low >= eps) where eps is 1e-10.
The second way to do this is to binary search over the integer part of the answer and then manually check for the decimal upto 6 places. This is what I had done. You can check out my solution here.
https://www.codechef.com/viewsolution/37276740
1 Like
Can you please provide the code of 1st approach that gives AC.
Hey ! Thanks for your reply. I tried implementing the first approach you mentioned but it still isn’t working. Can you point out the mistake ?
https://www.codechef.com/viewsolution/37300972
You need not update ans at each iteration. the final answer will be lo only. Also, i fixed the number of iterations without bothering the second condition of the difference of hi and lo. Also, try after using setprecision.
1 Like
https://www.codechef.com/viewsolution/37301538
I made a few changes to your code. This is like the standard way to implement binary search on doubles. Hope you get it now.
2 Likes
Look at these. Very helpful. This type of problems are quite standard in binary search and the technique is quite well explained here.
1 Like
Thanks a lot !.. I tweaked my original code and just put a setprecision(10) while ouputting the answer and it worked.
https://www.codechef.com/viewsolution/37322245
Just changed one line :
maxNum = max(maxNum+mid, a[i] + mid);
1 Like
Thank you very much.