Ternary Search Problem Codeforces Prob C DIv1 Round 320

1

Here is the link to the problem:
Prob C Div 1
Here are the links to my 2 submissions:

  1. WA On Test Case 26
  2. TLE On Test Case 4

So, I tried solving this question using ternary search as explained in the editorial to this problem.

Here is the link to the editorial of this problem:
EDITORIAL

I have implemented a very simple ternary search in my code. I made the difference between the left limit and the right limit as small as 10^(-9). However, I was still getting the wrong answer on Test Case 26. My answer was only correct up to 5 decimal places of the actual answer but the requirement was that the answer should be correct up to 6 decimal places. I tried to increase the search space by reducing the difference between the left limit and right limit even more. But then my code started giving TLE on test case 4.

I just want to know how do we fix precision issues like these in ternary search or in competitive programming in general.

A little help or some suggested resource that I could look at would really help me. I have never faced precision issues like these before and therefore I am really inexperienced in this.

If you could also have a look at my code to understand what I am trying to do would make things clearer.

THANKS IN ADVANCE.

2

With doubles and binary/ternary search, it’s almost always a good idea to have a fixed number of iterations rather than going until the difference reaches some \epsilon, because the precision in doubles might make it so that loop may never end.

Sometimes, also, using long doubles may be necessary

3 Likes
3

Thanks a lot for this wonderful advise. I will keep this in mind while doing a binary or ternary search next time. I just had one more doubt. If I keep reducing the value of E my answer should become more and more accurate right? I mean I should be getting better answers by reducing the value of E right?