Help needed in understanding Ternary Search

help
,
1

Hii guys!
I read this article and was trying the first practice problem. I am not able to figure out when to apply ternary search. It would be great if someone can explain me using this problem.
Thanks :slight_smile:

2

In this problem, the equation that gives the position of some car at a given point in time will be straight line. You need to find the time where the difference between the highest line and the lowest line is minimised. There is an interesting property that the highest and lowest lines will follow.

If you look at the line with the highest value at different time intervals, you will find that as the time increases, the slope of the line with the highest value is also increasing.

It’s actually even more intuitive if you think in terms of this problem, suppose that some car is leading in the beginning, and after some time some other car takes the lead, this new car’s speed must be greater than the previous one right ? (for it to be able to overtake), similarly if some car is leading at some point in time, its speed must have been higher than the one that was previously leading.

Lets get back to straight lines now. So, the lines that will represent the leading cars will have increasing slopes as the time increases. Similarly, the lines that will represent the cars with the lowest positions will have decreasing slopes as time increases.

alt text

The lines representing the leading cars and the cars that are behind at successive points in time will form the upper and lower envelope as shown. You need to find the point where the difference between them is minimised, as you can see, this difference between the envelopes is convex. So, this difference will decrease, reach a minimum and then start increasing. You can use ternary search to find the point where the difference is minimised.

2 Likes
3

Thanks a lot for the effort you put in for a detailed explanation :slight_smile:

1 Like
4

Thanks for the great article on ternary search. Also, the problem is ideal for practicing this algorithm.

The article is self-explanatory. I hope, I need not add anything more to it.

Ternary Search solution: https://www.codechef.com/viewsolution/18581461

Approach:

  1. I have designed a method ‘calc()’ which accepts a time t as an input parameter and linearly traverses the given array to find the max and min distance covered by any racer at time t. It then returns the difference of the distance. Complexity: O(N).
  2. Now, I have applied ternary search exactly as directed in the article on time t to determine the point of time at which the method ‘calc()’ returns the minimum value. Complexity: O(log(N)). [1000 iterations are also enough to pass the TL].

Overall complexity: O(N log(N)).

My solution: https://www.codechef.com/viewsolution/18581374

Approach:

  1. Method ‘calc()’ is same.
  2. I have implemented the traditional binary searching algorithm, that I have been using since the Stone age! For this trick, I have compared the value of calc(mid) with calc(mid-x); where x is a teeny-tiny value (1e-10). If the value of calc(mid-x) is lesser, I have assumed that the depression lies between l and mid, otherwise between mid and r.
1 Like
5

Thanks for a great explanation :slight_smile:
I was unable to understand why does one apply ternary search here. I guess I need to be more intuitive or learn some math xD.
Thank you again for the effort you put in!