Уровень 2. Сортировки и поиск

Классические приёмы, которые встречаются почти в каждой олимпиадной задаче: сортировки, два указателя, префиксные суммы и бинарный поиск.

Четыре приёма этого уровня — рабочие лошадки всех олимпиад: сортировка как инструмент, два указателя, префиксные суммы и бинарный поиск. Почти каждая задача «на смекалку» начального уровня решается одним из них или их комбинацией. Критерий готовности к уровню 3: вы узнаёте эти приёмы в незнакомых задачах — «отсортированный массив и пары» наводит на два указателя, «много запросов суммы» — на префиксы, «минимальное X, при котором возможно» — на бинпоиск по ответу.

В этом разделе

  1. 1
    Сортировки

    Сортировка как инструмент: std::sort, компараторы, сортировка структур.

  2. 2
    Метод двух указателей

    Метод двух указателей: пары с заданной суммой и скользящее окно за O(n).

    1 задач

  3. 3
    Префиксные суммы

    Префиксные суммы: ответ на запрос «сумма на отрезке» за O(1); разностный массив.

    1 задач

  4. 4
    Бинарный поиск

    Бинарный поиск по массиву и по ответу: O(log n), инварианты и типичные ошибки.

Доска