Занятие №4. Алгоритмы сортировки

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

Практика:                                         [Официальная страница]
Учебные задачи:
   Задача A. 
   [Пузырьковая сортировка: количество обменов]
   Классическая задача на пузырек. 
   Задача B.  
   [Разные]
   Еще одна классическая задача, для которой нужно применить квазилинейную сортировку. 
   Задача С. 
   [Объединение последовательностей]
   Задача на слияние двух отсортированных массивов. 
Олимпиадные задачи:
   Задача A. 
   [Ожерелье]  
   Довольно занятная задача. Пришлось подумать. Пока думал настрогал прожку, которая bfs’ом находит оптимальную стратегию. Только после этого решение стало очевидно).
   Задача B.
   [Головоломка] 
  Очень любопытная задача. Интересно всегда наблюдать за тем, как люди(и я в том числе) пишут симулятор разгадывания головоломки с помощью DFS или BFS, а потом с криками матерного содержания переписывают решение за 3 минуты и получают законные Accepted.  
  Задача С. 
  [НГУ-стройка]
  Задача кажется с первого взгляда неприступной. Но если хорошенько присмотреться, то все не так страшно. Первое что нужно понять, как будет выглядеть сечение блоков, если зафиксировать конкретное значение Z. Это будет набор взаимно непересекающихся прямоугольников. Чтобы проверить покрывают ли эти прямоугольники всю область достаточно найти сумму их площадей. Общая идея решения изложена в лекции п.9. Сканирующая прямая.
Дополнительные олимпиадные задачи:
   Задача A.  
   [Эльфы и олени] 
   Одна из тех задач, где жадность приводит к правильному ответу. Сортируем в порядке неубывания массив эльфов и оленей. Бинарным поиском подбираем K - количество оленей, которые попадут в упряжку. Чтобы проверить можно ли запрячь K оленей применяем следующую эвристику. Выбираем K минимальных эльфов и K максимальных. Группируем этих 2K эльфов по парам, чтобы обеспечить максимальное покрытие диапазона, которые занимают эльфы. Получаем: (1, N – K + 1), (2, N – K + 2) и т.д., где N – количество эльфов. С учетом выбранных пар утверждаем, что никакое другое деление на пары не увеличит количество оленей в ответе. Далее необходимо фиксировать выбранную пару эльфов и искать для него минимально возможного оленя.
Приведенное решения полностью идентично разбору Александра Чистякова с одним отличием, что для фиксированной пары эльфов можно находить оленя за O(logM) с помощью функции lower_bound, а не за O(M).
   Задача B.
   [Субботник]
   Сортируем человечков по росту. Бинарным поиском по ответу подбираем ответ на задачу, а именно наименьшее возможное значение максимального числа неудобства. Для того, чтобы проверить корректность выбранного ответа последовательно перебираем слева направо группы из подряд идущих С человечков. Считаем количество групп, которые удовлетворяют выбранному ответу. Если их количество не меньше заявленного в условии R, то выбранный ответ является корректным. Такая жадность дает корректный ответ.
   Задача С.
   [Палиндром]
   Довольно простая задача на сортировку подсчетом.