notTehlka's blog

Ternary Search
By notTehlka, history, 3 years ago, In English

Can someone please explain where can one use ternary search in a question. CP Algorithm states that ternary search is used when function f(x) which is unimodal on an interval [l,r]. But my question is how can one tell whether this condition holds or not? Is there some specific way?

Is ternary search applicable in this Div3 G. If yes, then how?

  • Vote: I like it
  • +23
  • Vote: I do not like it

»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

quadratic functions

→ Reply
»
3 years ago, # |
  Vote: I like it +5 Vote: I do not like it

For problem G you need just to extend the codomain of f(x) from integers to real numbers. 119051522

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

I think we can extend the idea of binary search to apply ternary search in this question. The only difference will be that in each step the search space will reduce by 2N/3 instead of N/2. And the check function will return a boolean value saying if the answer can be greater than or equal to this number. Here's the implementation of the above idea : 119161328

→ Reply