ALIEN INVASION HELP!

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 !

https://www.codechef.com/viewsolution/37300536

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

https://codeforces.com/edu/course/2/lesson/6

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/37302380

Code

I did quite similar, getting wrong answer on internal test cases. Can you help?

https://www.codechef.com/viewsolution/37322245

Just changed one line :
maxNum = max(maxNum+mid, a[i] + mid);

1 Like

Thank you very much.