Бен поиск 0:00 Обсуждение задачи поиска числа, которое меньше заданного числа. Предлагается использовать бинарный поиск для решения задачи.
Бен поиск по ответу 14:22 Обсуждение задачи о двух принтерах, которые печатают страницы за разное время. Предлагается использовать бен поиск для определения минимального времени, необходимого для печати всех страниц.
Тернарный поиск 20:02 Рассматривается задача поиска максимума на отрезке, где функция монотонна. Идея состоит в том, чтобы сдвигать границы отрезка так, чтобы в конце концов они сошлись на одной точке. Если функция возрастает, то максимум находится между двумя соседними точками. Если функция убывает, то максимум находится между двумя соседними точками, где оба соседа меньше.
Дискретный массив 33:37 Рассматривается задача поиска максимума на массиве, где элементы возрастают, достигают максимума, а затем убывают. Идея состоит в том, чтобы построить функцию, которая показывает, что элемент меньше следующего с меньшим значением на единицу. Затем используется бинарный поиск для поиска максимума на отрезке.
Поиск максимума функции 37:32 В видео обсуждается поиск максимума функции на отрезке. Производная функции в точке максимума равна нулю, и это используется для нахождения точки максимума.
Бен поиск 40:24 Для поиска точки максимума используется метод бен поиска. Бен поиск приближает производную функции, и если значение функции в точке x + epsilon больше, чем в x, то левая граница сдвигается. Если значение функции в x + epsilon меньше, чем в x, то правая граница сдвигается.
Уточнение алгоритма 47:11 В видео объясняется, как изменить алгоритм бен поиска, чтобы он работал за логарифм от n. Это достигается путем деления epsilon на два в каждой итерации.
Тернарный поиск 55:02 В видео обсуждается тернарный поиск, который используется для нахождения максимума функции. Важным моментом является то, что равные значения функции должны возникать только когда между ними находится максимум. Это позволяет избежать ошибок при поиске максимума.
Сложный тернарный поиск 1:00:55 В видео объясняется, как можно использовать тернарный поиск для функций двух аргументов, если функция имеет только один максимум. В этом случае можно сначала найти максимум по одной переменной, а затем по другой.
Решение задачи с поиском 1:07:36 В видео рассматривается задача поиска последней единицы в последовательности чисел. Для решения этой задачи используется тернарный поиск, который позволяет найти позицию единицы и затем перейти к следующей единице.
Алгоритм поиска позиции 1:12:24 Функция "чек" возвращает true, если ответ больше, чем x. Алгоритм ищет позицию, где ответ равен x, используя степени двойки. Если ответ больше, чем x, прибавляется 1 к степени двойки.
Уменьшение степени двойки 1:26:37 Алгоритм уменьшает степень двойки каждый раз, когда ответ больше, чем x. Если ответ меньше, чем x, степень двойки увеличивается.
Вывод чисел 1:27:36 Использование магических строк для ускорения вывода чисел. Вывод чисел с точностью до 15 знаков.
Интерактивные задачи 1:30:26 Если программа должна взаимодействовать с пользователем, нужно использовать вывод и ввод. Интерактивные задачи требуют постоянного общения с программой.
Обсуждение кода и оптимизации 1:32:21 Автор обсуждает использование символов перевода строки и предлагает использовать их для удобства. Он также обсуждает использование longlong и long для оптимизации кода.
Использование define и using 1:36:16 Автор объясняет, что define и using - это разные вещи, и использование define может привести к ошибкам. Он рекомендует использовать using для оптимизации кода.
Обсуждение алгоритмов и задач 1:41:01 Автор обсуждает алгоритм бинарного поиска и его применение в задачах. Он также упоминает о прагмах и их использовании в олимпиадах.
