How to solve/prove this type of problems?

Revision en1, by parth_15, 2019-01-13 13:53:34

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.

Tags ternary search, proof, problem solving

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English parth_15 2019-01-13 13:53:34 1047 Initial revision (published)