Что решает
подсчёт вариантов
Статьи
DP
Приём
Динамическое программирование
Сводим задачу к подзадачам, решаем каждую один раз и храним ответы в таблице.
состояния × переходы
2 задачи
DP
Приём
Динамика по маскам
Состояние — подмножество, записанное битами числа: точный коммивояжёр, назначения, раскладки по профилю.
O(2ⁿ · n²) для коммивояжёра
2 задачи
DP
Приём
Динамика по цифрам
Счастливые билеты в любом диапазоне за проход по цифрам: 55 252 из миллиона и любой из 10¹⁸ — за миллисекунду.
O(D · 10 · S)
2 задачи
NUM
Алгоритм
Китайская теорема об остатках
Число по остаткам от нескольких модулей: алгоритм Гарнера и точные вычисления по многим простым.
O(k²) операций с машинными числами
2 задачи
NUM
Алгоритм
Матрицы и рекуррентности
Степень матрицы: пути длины k в графе, линейные рекуррентности, матрица переноса и цепи Маркова.
O(m³ log k) для A^k размера m × m
2 задачи
ML
Алгоритм
Наивный Байес
Считает, как часто каждый признак встречается в каждом классе, и складывает логарифмы этих частот.
O(N) обучение, O(L·m) ответ
2 задачи
Задачи
Две книги на сертификат
Маршруты без шагов назад
Определитель языка
Пары ближе r
Пары из корзин
Ровно ноль градусов
Сайты на кольце
Сайты с буквой N
Сколько останется схем
Сколько треугольников
Сколько умножений цифр
Словарное разнообразие
Текст без пробелов
Частые слова за один проход
Без сдачи
Все остовные деревья
Где может лежать k-й
ДНК без участка рестрикции
Забытый код
Лифт без четвёрок
Параллельные пары
Перекрёсток на ремонте
Подарок к покупке
Сколько раз выполнится строка
Сколько разных кусков
Счастливые в диапазоне
Счёт по перестановке
Счётчик сравнений
Треугольники импортов
Фильтр учится на ходу
Хвост суммы кубиков
Цепочки рейсов
Штрихи на рейке
Сколько оснований лгут
Сколько раз каждое слово
Сколько раскрасок
Часто рядом
классика 5 динамика 4 олимпиады 4 карты и навигация 3 оптимизация 2 собеседования 2 теория чисел 2 линейная алгебра 2 матрица 2 граф 2 мемоизация 1 ациклический граф 1