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?
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 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 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 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 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 22.12.2024 15:15:29 (i1).
Десктопная версия, переключиться на мобильную.
При поддержке
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.