I was solving the Race Time ! problem at AMCS03 Problem - CodeChef and could finally solve it using ternary search (I found the link to this problem under the practice section of a website under the ternary search topic) but I am unable to prove that why does ternary search work for this problem. In other words I am unable prove that this function is unimodal. How can one go about proving whether a function is unimodal or not? And in particular how do I prove this function as unimodal?
@utkarsh1729 I think the function should be bimodal and here is the link for your reference to the Editorial.
1 Like
@rishup_nitdgp Thanks for the link to the editorial. But I certainly don’t understand the proof given over there. It seems I will have to brush up on my knowledge of the mathematics involved in the proof. By the way, a more intuitive proof or even a simple explanation as to why Ternary Search works for this problem will serve my purpose at the time being. Once again, thanks for responding.
Firstly, we know the function wants us to find the minimum distance between the first and last cars.
Imagine there are 2 cars, but the car in the front may increase it’s speed, and the car at the back may decrease it’s speed. The distance will only reduce until the car at the front becomes faster than the car at the back.
(For now assume the car at the back doesn’t overtake the car at the front).
It’s easy to see after this the car at the back cannot become faster than the car at the front, so the distance will only increase, So the distance decreases then increases.
We also know, That to overtake another car, You need to be faster than it. So the interpretation is when a car overtakes, It will have the same distance, But a larger speed, which is what we called an increase in speed. And when the last car overtakes some other car, The new car at the last position must have a smaller, speed, Which was the decrease in speed.
The initial car at the back won’t overtake because our 2 initial cars are imaginary, they represent the car in first place and the car at last place.
1 Like