Задачник Базовый курс EN

Как устроен

битовые трюки

Статьи

SRT Алгоритм Timsort Находит готовые упорядоченные куски и сливает их: стек серий, галоп, powersort. O(n log n), на готовых данных O(n) 2 задачи SRT Алгоритм Сортировка подсчётом и поразрядная Без сравнений: посчитать ключи или разложить их по цифрам — O(n + k) и O(d·n) вместо n log n. O(n + k) и O(d·(n + b)) 2 задачи DS Структура данных Дерево Фенвика Суммы на префиксе с изменениями за O(log n) в одном массиве: блоки длиной в младшую единицу номера. O(log n) на сумму префикса и на изменение 2 задачи DS Структура данных Разреженная таблица Минимум любого отрезка за O(1) после O(n log n) подготовки: два перекрывающихся блока длиной 2^k. O(1) на запрос, O(n log n) на построение 2 задачи GRA Алгоритм Наименьший общий предок Общий предок двух вершин дерева: двоичный подъём за O(log n), обход Эйлера за O(1), Тарьян офлайн. O(log n) на запрос 2 задачи DP Приём Динамика по маскам Состояние — подмножество, записанное битами числа: точный коммивояжёр, назначения, раскладки по профилю. O(2ⁿ · n²) для коммивояжёра 2 задачи NUM Алгоритм Быстрое возведение в степень aⁿ за O(log n) умножений: квадраты по битам показателя. O(log n) умножений 2 задачи NUM Алгоритм Генераторы псевдослучайных чисел Откуда берутся «случайные» числа, почему плохой генератор видно по плоскостям и как его проверить. O(1) на число 2 задачи GEO Приём Кривые Гильберта и geohash Пронумеровать плоскость так, чтобы соседи на карте стояли рядом в одномерном индексе: Z-порядок, geohash, Гильберт. O(k) на номер 1 задача TEC Приём Битовые трюки Число как набор флажков: маски, младшая единица, подсчёт единиц и перебор подмножеств без рекурсии. O(1) на операцию над словом 1 задача TEC Приём Предподсчёт и таблицы Посчитать ответы заранее и брать из таблицы: CRC-32 байтом за шаг вместо бита и где таблица перестаёт помогать. O(размер таблицы) один раз, затем O(1) на запрос 1 задача

Задачи

Адреса по порядку Оценка по хешам Права доступа CRC по строкам Банк головоломок Маршрут по кривой Гильберта Серии Timsort Сжатый список вхождений Сколько останется схем Следующее число Счётчик туда-обратно Декодер Какие серии слить Кому какой заказ Погасить все лампочки Проверка доказательства Расшифровка по длинам кодов Самый длинный пролёт Сообщение через шум Экскурсия по дереву жизни Грузовой лифт Дни экзаменов Загрузка по порядку Снегоуборщик

Часто рядом

классика 8 в проде 5 олимпиады 5 массив 3 собеседования 3 предподсчёт 3 сортировка 2 устойчивость 2 префиксные суммы 2 контроль версий 2 запросы на отрезке 2 наука и физика 2