ternary search emergency

Revision en2, by bhikkhu, 2016-11-04 08:48:27

http://codeforces.com/contest/439/problem/D

Ternary search can only be used on strictly increasing or decreasing sequence.

But, I think the problem is special in the sense that the search space is strictly decreasing first then some equal values and then strictly increasing.

Thus, ternary search can be used here. But I need to prove that if two f(p) == f(p + 1), then the value must be the answer (if f(p) == f(p + 1), f(p) = our_answer to the problem, in case f(p) = f(p + 1) for any p).

Tags ternary

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English bhikkhu 2016-11-04 08:48:27 91
en1 English bhikkhu 2016-11-04 08:46:58 436 Initial revision (published)