жадность

Статьи

SRT Приём Двоичный поиск по ответу Если проверить ответ легче, чем найти, и проверка монотонна, — ищем ответ делением пополам. O(log D · стоимость проверки) 2 задачи GRA Алгоритм Алгоритм Дейкстры Кратчайшие пути от одной вершины во взвешенном графе без отрицательных рёбер. O((V + E) log V) 3 задачи GRA Алгоритм Минимальное остовное дерево Самая дешёвая сеть, связывающая все вершины: Борувка, Краскал и Прим — три способа применить одну лемму. O(E log V) 2 задачи GRA Алгоритм Раскраска графа Соседям — разные цвета: жадный способ, порядок «наименьший последним», DSatur и точный перебор на картах и расписаниях.

O(V + E) — жадно в данном порядке и «наименьший последним»; O((V + E) log V) — DSatur с кучей

2 задачи STR Алгоритм Diff Майерса Кратчайший сценарий удалений и вставок строк за O((N + M) · D): волны по числу правок. Так работает git diff. O((N + M) · D) 1 задача STR Алгоритм Код Хаффмана Оптимальный префиксный код по частотам знаков: два самых редких дерева склеиваются, пока не останется одно. O(n log n) 2 задачи STR Алгоритм LZ77 и LZW Повторы — ссылками назад (LZ77) или номерами фраз растущего словаря (LZW); хеш-цепочки, уровни, окно. O(n · chain) 2 задачи DP Алгоритм Задача о рюкзаке Лучший набор вещей под ограничение по весу: таблица n × W и путь по ней назад. O(n·W) 3 задачи DP Алгоритм Наибольшая возрастающая подпоследовательность Самая длинная растущая цепочка элементов в исходном порядке: пасьянс и двоичный поиск за n log n. O(n log n) 2 задачи DP Алгоритм Seam carving Сужает фото, вырезая пиксельные швы наименьшей энергии; каждый шов — динамика по таблице. O(W·H) на шов, O(k·W·H) на k швов 2 задачи DP Алгоритм Красивый перенос строк Жадный перенос против всего абзаца сразу: кратчайший путь по местам разрыва, как в TeX. O(n·L) 2 задачи PAR Приём Жадные алгоритмы Лучший шаг сейчас без оглядки назад: когда это оптимально, когда почти, и как это доказать. обычно O(n log n): сортировка или куча 2 задачи SYS Алгоритм Планирование задач Порядок работы: короткие сначала, сроки, прерывания, много ядер и аномалии Грэма. O(n log n): сортировка или куча 2 задачи ML Алгоритм Решающее дерево Отвечает цепочкой вопросов «признак ≤ порог?»; каждый вопрос выбран так, чтобы неопределённость упала сильнее всего. O(h · F · n log n) построение; O(h) ответ 2 задачи

Задачи

Выравнивание полей Коробки в архиве Лучший первый вопрос Районы электросети Роман за k дней Сколько бит займёт текст Сколько нужно залов Станции проката Дальность дрона Дерево по Джини Запас ведра Заправки по пути Индекс из прямых Кратчайший остаток Ровный заголовок Ровный правый край Склейка Сколько строк поменялось Сколько успеть к сроку Частоты для вышек Нумерация глав Рулон кабеля

Часто рядом

классика 13 собеседования 7 в проде 6 куча 5 динамика 5 олимпиады 4 кратчайший путь 4 граф 4 двоичный поиск 3 оптимизация 3 расписание 3 приближение 3