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?
→ Pay attention
→ Streams
→ Top rated
| # | User | Rating |
|---|---|---|
| 1 | tourist | 3985 |
| 2 | jiangly | 3814 |
| 3 | jqdai0815 | 3682 |
| 4 | Benq | 3529 |
| 5 | orzdevinwang | 3526 |
| 6 | ksun48 | 3517 |
| 7 | Radewoosh | 3410 |
| 8 | hos.lyric | 3399 |
| 9 | ecnerwala | 3392 |
| 9 | Um_nik | 3392 |
→ Top contributors
| # | User | Contrib. |
|---|---|---|
| 1 | cry | 169 |
| 2 | maomao90 | 162 |
| 2 | Um_nik | 162 |
| 4 | atcoder_official | 161 |
| 5 | djm03178 | 158 |
| 6 | -is-this-fft- | 157 |
| 7 | adamant | 155 |
| 8 | awoo | 154 |
| 8 | Dominater069 | 154 |
| 10 | luogu_official | 150 |
→ Find user
→ Recent actions
Codeforces (c) Copyright 2010-2024 Mike Mirzayanov
The only programming contests Web 2.0 platform
Server time: Dec/22/2024 10:04:02 (g1).
Desktop version, switch to mobile version.
Supported by
Auto comment: topic has been updated by Brodicico (previous revision, new revision, compare).
When I see that U shape structure, Increases both side but optimal at some middle structure.. I almost assume its ternary search..
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.
Very cool aproach man!
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.
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://mirror.codeforces.com/blog/entry/43440
Notice the logic for determining which side to recurse on is really a difference quotient, a discrete derivative, slope etc.