Тренер по программированию

Решим простую задачу на графы, которая на первый взгляд такой не кажется. Сначала читаем развесистое условие и пытаемся понять, что требуется в задаче: Если переложить на язык алгоритмов, то надо покрыть граф путями. И есть специальные алгоритмы, которые справляются с этой задачей. Но они расчитаны на ориентированные графы. А в этой задаче по каждой дороге можно передвигаться в обоих направлениях. Если упростить задачу и сказать, что есть только один ковбой и спросить, можно ли заблокировать все дороги? Тогда мы получим вариант классической загадки про нарисовать фигуру, не отрывая руки...

Сегодня решим сложную задачу на динамическое программирование про поиск уникальных подпоследовательностей. Читаем условие: Сложность задачи складывается из нескольких пунктов: Напомню, что подстрока - это непрерывная последовательность символов с i-го до j-го. Или, на языке Python - это слайс s[i:j]. А подпоследовательность - это любая последовательность, которая может быть получена из исходной вычёркиванием произвольного числа символов. Количество подстрок O(N^2), а количество подпоследовательностей O(2^N), поэтому перебрать все не получится...

Давно не было решений на С++. Сегодня разберём непростую задачу на динамическое программирование по подмножествам, которую на Python затолкать в ограничения очень сложно. Читаем условие: Почти всегда, когда в задаче есть перебор перестановок, можно решение за O(N!) заменить решением за O(N * 2^N), используя динамическое программирование по подмножествам. Это всё ещё экспоненциальное решение, но константа сильно меньше. В нашем случае, если решать задачу в лоб, то надо каждую перестановку ещё проверять на удовлетворение условий К-перестановки...

Разберём решение ещё одной задачи на динамическое программирование, в которой нет ничего сложного, и можно рассмотреть все шаги решения таких задач. Сначала читаем условие: Алгоритм решения будет точно таким же, как и в задачах Задача 11. Зайчик и Задача 29. Компьютерная игра. Но здесь есть дополнительные ограничения, поэтому рекомендую разобраться с теми задачами и потом вернуться сюда. Как обычно, сначала надо определиться, что будет состоянием динамики. Выберем в качестве состояния длину префикса введённого числа...