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

На чём держится

ациклический граф

Статьи

GRA Алгоритм Топологическая сортировка Выстраивает вершины графа без циклов так, чтобы все рёбра смотрели вперёд, за O(V + E). O(V + E) 2 задачи GRA Алгоритм Компоненты сильной связности Группы вершин, где из любой можно дойти до любой: Тарьян за один обход, Косараю за два, O(V + E). O(V + E) 2 задачи DP Приём Динамическое программирование Сводим задачу к подзадачам, решаем каждую один раз и храним ответы в таблице. состояния × переходы 2 задачи DP Алгоритм Seam carving Сужает фото, вырезая пиксельные швы наименьшей энергии; каждый шов — динамика по таблице. O(W·H) на шов, O(k·W·H) на k швов 2 задачи DP Алгоритм Алгоритм Витерби Самая правдоподобная цепочка скрытых состояний по шумным наблюдениям: улицы по GPS, участки генома, сообщение по битам. O(T · S²) 2 задачи DP Алгоритм Красивый перенос строк Жадный перенос против всего абзаца сразу: кратчайший путь по местам разрыва, как в TeX. O(n·L) 2 задачи SYS Алгоритм Часы Лэмпорта и векторные часы Логические часы: одно число Лэмпорта согласовано с «случилось раньше», вектор по процессам отличает «раньше» от «параллельно». O(1) на событие у Лэмпорта, O(n) у векторных 2 задачи

Задачи

Векторные отметки Маршруты без шагов назад Сколько семестров Лавина повторов Недостающие улицы Что прочитать Нумерация глав

Часто рядом

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