# конспект · шаг 7 из 7
Конспект: как узнать задачу и найти готовое решение
Понятия
Сведение - перевести вход своей задачи во вход известной, вызвать известный алгоритм, перевести ответ обратно. К лёгкой задаче - верхняя оценка («не дороже»), к трудной - нижняя (раздел 21).
Неявный граф - соседи вершины вычисляются на лету, граф целиком нигде не хранится.
Наибольшая возрастающая подпоследовательность (НВП) - самая длинная строго возрастающая цепочка
элементов в порядке списка. Прямо - хвостами и двоичным поиском за n log n.
Признак - слово формулировки, которое называет кандидата в методы. Кандидат принимают, только проверив его условие.
OEIS - энциклопедия целочисленных последовательностей (oeis.org): ряд → формула, рекуррентность, задачи.
Монотонная очередь - номера кандидатов в максимум с убывающими значениями; максимум окна за O(1),
весь проход за O(n).
Что унести
СВЕДЕНИЕ
перевод туда -> известный алгоритм -> перевод обратно (и «ответа нет»)
цена = переводы + известный; дешёвые переводы оценку не меняют
конь 8×8 угол-угол: 6 ходов; угол - [1, 1]: 4; граф неявный
НВП, n = 200: через LCS 36 400 клеток, хвостами 787 сравнений
сведённое решение = эталон для сверки прямого
ПРИЗНАК -> КАНДИДАТ -> УСЛОВИЕ
минимизировать максимум -> поиск по ответу -> монотонность
наименьшее число шагов -> поиск в ширину -> рёбра одной цены
кратчайший, веса >= 0 -> Дейкстра -> нет минусов
порядок с зависимостями -> топосортировка -> нет циклов
сколько способов -> динамика -> подзадачи повторяются
n <= 20 -> маски, перебор -> 2ⁿ в бюджете
конвейер 12 заданий: C(11, k-1) разрезов против 5-6 проверок
BFS на взвешенном: 50 минут вместо 40 - ответ правдоподобный и неверный
РЯД МАЛЕНЬКИХ СЛУЧАЕВ
перебор n = 1..8 -> ряд -> OEIS / каталог Скиены (75 задач) / раздел 21
скобки и рукопожатия: 1, 2, 5, 14, 42 -> Каталан, C(2n, n) / (n + 1)
верят, когда видна рекуррентность K(n) = Σ K(i)·K(n-1-i)
области круга: 1, 2, 4, 8, 16, 31, 57 = 1 + C(n,2) + C(n,4), не 2ⁿ⁻¹
гипотезу проверяют на членах, по которым её не строили
ПОВТОРНАЯ РАБОТА В ПЕРЕБОРЕ
поиск среди всех -> сортировка, словарь, двоичный поиск
перекрывающиеся куски -> обновление на ходу, префиксные суммы
одна подзадача много раз -> запоминание, динамика
пары с разницей <= d, n = 200: 19 900 проверок -> 391 (+ сортировка)
максимум окна, k = 100: 20 100 -> 593, почти не зависит от k
Ловушки джокера
Сведение, принятое за оптимум. Оно говорит «не дороже», а не «не быстрее»: НВП через LCS в 46 раз медленнее прямого алгоритма.
Перевод потерял «нет». Известная задача всегда возвращает число, а в своей ответа может не быть.
Метод по слову. Поиск в ширину на дорогах разной длины, двоичный поиск по немонотонному признаку - правдоподобный ответ без единой ошибки в логах.
Формула по пяти членам. Удвоение «очевидно» до шестого члена.
Не то лекарство. Сортировка уничтожает порядок, в котором живут окна.
Левый указатель возвращается назад. Два указателя со сбросом в цикле - снова n².
Комментарии
Пока нет комментариев. Будь первым!
Оставить комментарий