Brodicico's blog

Signs of using ternary search
By Brodicico, history, 5 years ago, In English

Hello Codeforces. I've analyzed a lot of solutions of today's problem E (round 643) and at a lot of them i've seen ternary search. I understood why binary search can't work in this scenario, but can someone please give me some good explanation on when whe should use ternary search? Maybe some signs which instantly tells us that ternary search should be used?

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

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Brodicico (previous revision, new revision, compare).

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

When I see that U shape structure, Increases both side but optimal at some middle structure.. I almost assume its ternary search..

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

I never learned ternary search before but I solved today's E question with binary search (my submission: 80368801).

When I iterated over the final target height I noticed that the total cost was decreasing and then increasing, so I suppose that a function with this property can be minimized with ternary search.

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

As far as I know, it is used to find the only maxima/ minim of a concave/ convex graph traced out by an evaluation function on various inputs. here is a detailed solution of codeforces problem, trying to explain the ternary search in more deatail.

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

Binary search is for monotonic functions. Ternary search is for unimodal functions. It must be strict unimodal else the search will halt as soon as it finds a plateau (0 slope). Note every strictly monotonic function is a degenerate unimodal function (with no left or right tail) so ternary search will work when binary search does as long as the monotonicity is strict. Here is some code: https://codeforces.me/blog/entry/43440

Notice the logic for determining which side to recurse on is really a difference quotient, a discrete derivative, slope etc.

→ Reply