Hello all. I know that ternary search can be applied when function is monotonic and can be used to find maximum/minimum value of function. But, for some problems that can be solved with it, how to prove that it is monotonic. Is there any general technique or you only visualize by graph.
For ex: I was solving problem and making graph of it, I get some idea that it is decreasing and then increasing but I can't prove it strictly. In the editorial, they mentioned that f+g is monotonic if f is strictly increasing and g is strictly decreasing. I am also not able to get that proof and I asked on stackexachange and the answer was it was not true. Then how it is proved in editorial. Can someone help with this questions? Thanks in advance.
Binary search assumes the function you search on is monotonic. Ternary search assumes the derivative of the function you search on is monotonic.
The reason for which what you said isn't true:
f is increasing and g is decreasing, therefor f' is always positive and g' is always negative (using the tag' for derivative). Let h = f + g, then h' = f' + g'. We are hoping to show that h' is monotonic for ternary search, but the information about f', g' is not enough (we can make h' jump between positive and negative repeatedly, for instance).
As for your problem: we have the function
and we look only at x1 ≤ t ≤ x2, since anything else is suboptimal. (Also we can assume that x1 ≤ x2, otherwise we can swap and the answer won't change).
We have more information than just monotonicity for each term. If you want to prove that you can use binary or ternary search, you should probably analyze this function.
It really depends on the problem, but for the purpose of contest many people just see it intuitively.
You can always separate the function into chunks and run ternary search based on some value computed for each chunk. It's a cool heuristic and great idea.
this xd
Thanks, I was looking for that!