Занятие №3. Алгоритмы поиска в олимпиадных задачах

Теория: Лекция                                             [Все занятия]

Лекция шикарная. Особо понравилось описание “бинарного поиска по ответу”. Также произвел впечатление описанный подход с выявлением радиоактивного шарика и нахождения фальшивой монеты.

Практика:                                         [Официальная страница]
Учебные задачи: 
   Задача A. 
   [Номер максимального элемента]
   Классика жанра. Даже не знаю, что еще можно добавить.  
   Задача B. 
   [Сложность двоичного поиска]
   Суть задачи сводится к нахождению значения log(n) по основанию 2, округленного в большую сторону.
   Задача С. 
   [Двоичный поиск]
   Классическая задача на проверку корректной реализации на бинарный поиск. Базовую реализацию и частные случаи бинарного поиска мы уже рассматривали ранее в этом посте. 
Олимпиадные задачи: 
   Задача A. 
   [Забавный конфуз]
   Задача на умение работать с одномерным массивом. 
   Задача B. 
   [Черепаха]
   Решение полностью соответствует авторскому разбору. Главное в задаче выделить монотонную функцию, применив затем к ней бинарный поиск для нахождения корней. Хороший пример, иллюстрирующий подход бинарного поиска по ответу.
   Задача С.
   [Очень легкая задача]
   Казалось бы задача, как задача. И даже разбор полный дан в лекции и сама по себе задача несложная. Но есть в ней один интересный момент. Перед дихотомией нужно чем то инициализировать верхнюю границу подбираемого значения. В первом своем решение я взял n*max(x,y), т.е. печатаем все страницы на самом медленном принтере. С типами все в порядке. B вдруг получаем TLE на последнем тесте. В исходнике двухлетней давности я взял в качестве этого параметра n*min(x,y). Казалось бы какая разница? Но старое решение заходит, а новое нет. Отмечу, что вычисления идут в интах.
Рассмотрим граничный тест: 2e8 10 9.
Инициализация:   l = 0;       r = 1.8e9
Первая итерация: l = 0.9e9+1; r = 1.8e9
Вторая итерация: l + r = 2.7e9 – Переполнение типа.
В итоге середина сойдется к числу меньшему 1e9. В старом решении не происходило переполнения типа только потому что после первой итерации дихотомии правая граница становилась 1e9 и в дальнейшем переполнение исключалось.
Такие случаи конечно нужно просчитывать предварительно, но чтобы спать спокойно сейчас я решил ее в long long’ах =)
Дополнительные олимпиадные задачи:
   Задача A. 
   [Медиана объединения] merge 
   С ходу можно предложить слияние двух массив в один отсортированный. Сложность merge O(N)
   [Медиана объединения] kth_element
   Также данную задачу можно решить с помощью нахождения k-ой порядковой статистики. Данный алгоритм имеет ту же линейную сложность, что и первое решение, но константа будет больше, т.к. имеют место копирование двух подмассивов в один.
   Задача B. 
   [Столица]
   Умение находить k-ую порядковую статистику в этой задаче может ускорить решение, но ограничения позволяют сделать полную сортировку. 
   Задача С.
   [Выборы]
  Шикарная задача. Суть задачи сводится к нахождению стоимости политической партии. Для каждой партии бинарным поиском подбираем количество голосов, которые необходимо набрать этой партии для победы. Далее с помощью функции lower_bound проверяем корректность выбранного количества голосов. В итоге имеем 2 сортировки, 2 бинсерча + очевидное ДП.