предподсчёт

Статьи

DS Структура данных Разреженная таблица Минимум любого отрезка за O(1) после O(n log n) подготовки: два перекрывающихся блока длиной 2^k. O(1) на запрос, O(n log n) на построение 2 задачи GRA Алгоритм A* Дейкстра с подсказкой «сколько ещё до финиша»: волна тянется к цели, а путь остаётся кратчайшим. O((V + E) log V) 2 задачи GRA Алгоритм Иерархии сжатия Предподсчёт навигаторов: сжимаем неважные перекрёстки в ярлыки и ищем путь двумя волнами вверх. O((V + E′) log V) 1 задача GRA Алгоритм Наименьший общий предок Общий предок двух вершин дерева: двоичный подъём за O(log n), обход Эйлера за O(1), Тарьян офлайн. O(log n) на запрос 2 задачи STR Алгоритм Префикс-функция и КМП Все вхождения образца за O(n + m) без шагов назад по тексту; префикс-функция находит и период строки. O(n + m) 2 задачи STR Алгоритм Z-функция Сколько букв от каждой позиции совпадает с началом строки — за O(n); поиск, периоды и повторы подряд. O(n) 2 задачи STR Алгоритм Бойер — Мур Сравнивает справа налево и перепрыгивает буквы: на длинных образцах читает лишь малую часть текста. O(n + m) 2 задачи STR Структура данных Суффиксный массив Отсортированные хвосты текста: поиск двоичным поиском, повторы и число разных кусков по соседям. O(n log n) 2 задачи NUM Алгоритм Решето Эратосфена Все простые до n за O(n log log n): вычёркиваем кратные каждого простого, начиная с его квадрата. O(n log log n) 2 задачи NUM Алгоритм Метод Гаусса Линейная система исключением: ведущий элемент, LU, обусловленность, разреженные матрицы и заполнение. O(n³): около n³/3 умножений на прямой ход 2 задачи GEO Алгоритм Точка в многоугольнике Луч из точки пересекает границу нечётное число раз — точка внутри; число оборотов — то же со знаками. O(n) на точку 2 задачи GEO Алгоритм Упрощение линий Рамера — Дугласа — Пекера Упростить ломаную без потери формы: точка, дальше всех от хорды, остаётся, если она дальше допуска. O(n log n) в типичном случае, O(n²) в худшем 2 задачи TEC Приём Префиксные суммы Сумма любого отрезка за O(1) после одного прохода; двумерный вариант считает сумму любого прямоугольника картинки. O(n) на построение, O(1) на запрос 2 задачи TEC Приём Предподсчёт и таблицы Посчитать ответы заранее и брать из таблицы: CRC-32 байтом за шаг вместо бита и где таблица перестаёт помогать. O(размер таблицы) один раз, затем O(1) на запрос 1 задача

Задачи

CRC по строкам Год по индикту Журнал обменов Звено повтора Как растёт список Python Праймер без двойников Простые в окне Самая длинная цепочка Коллатца Самый жаркий день Сколько прочтёт Хорспул Дальность дрона Запросы по ярусам Карта на всех масштабах Квадродерево снимка Общая папка Порог плотности Похожие пароли Размер блока Разрез по меридиану Расшифровка по длинам кодов Самый длинный пролёт Словарь опечаток Счётчик сравнений Таблица хорошего суффикса Цена поиска Цепочки рейсов Шов через пиксель Штрихи на рейке Экскурсия по дереву жизни

Часто рядом

классика 11 олимпиады 7 наука и физика 4 граф 4 карты и навигация 4 собеседования 4 в проде 4 поиск в тексте 4 массив 3 битовые трюки 3 биоинформатика 3 запросы на отрезке 2