[Базовый олимпиадный курс] Занятие 2. Динамическое программирование

Добрый день, уважаемые друзья!

На этот раз нашей темой будет динамическое программирование. Тема очень важная и обширная, поэтому одной лекцией Андрея Станкевича не исчерпывается. Однако, в для начала вам следует посмотреть его лекцию на youtube до воскресенья, а в воскресенье, 2 декабря, решить в виртуальном режиме следующий трехчасовой контест. Убедительная просьба условия до начала виртуального контеста не читать — хороших тренировок не так много и портить их себе не стоит.

Также напоминаю про соревнование Proggy-Baggy в субботу, 1 декабря.

Всем неравнодушным настоятельно советую Educational Codeforces Round 55. Контесты этой серии вообще пропускать не стоит, что напрямую следует из их названия.

Также напоминаю про необходимость добивания задач прошедших соревнований. Пока всего два студента занимаются дорешиванием первого контеста нашей тренировочной серии. Присоединяйтесь!

14 thoughts on “[Базовый олимпиадный курс] Занятие 2. Динамическое программирование

  1. По вопросам вступления в группу ОНУ на кодфорсе просьба писать под этим постом свой никнейм, чтобы я смог вас пригласить. Группа переходит в режим непубличной по причине наплыва иногородних/иностранных желающих вступить в нее.

  2. Поскольку я не присутствую на местности, не могу следить за плотностью вашего графика. Судя по тому, что пока что один человек написал тренировку по ДП, а вопросов, как участвовать в виртуальном соревновании, не последовало, я могу сделать вывод, что либо в связи с контестом в субботу у вас осталось мало времени на еще один контест в воскресенье, либо вы не прочитали пост номер два. Хочу получить ясную картину происходящего. В связи с простоем, пока что задание на следующее воскресенье остается прежним — посмотреть лекцию Станкевича по ДП и решить тренировку в виртуальном режиме.

  3. Разбор. A. Лестница

    Проинициализируем первые две ячейки динамики единственным возможным образом:

    Тогда значения в остальных ячейках будут вычисляться как максимум среди тех клеток, из которых мы можем туда прийти, плюс значение в текущей ячейке.

    Ответом является dyn[n]

  4. Разбор. B. Зайчик

    Заменим символы входной строки на числа: ‘.’ на 0, ‘»‘ на 1, ‘w’ на -1. Тогда данная задача будет мало чем отличаться от предыдущей за исключением того, что из -1 в текущую клетку прыгать нельзя. Добавим такую проверку. И ходы удобнее уже обрабатывать в цикле.

    Ответом является dyn[n - 1]

  5. Разбор. C. Ход конем

    Заметим, что $x$ и $y$ координаты коня как растут, так и убывают, поэтому нельзя рассматривать ячейки по возрастанию $x$ или $y$. Но зато сумма $x + y$ всегда строго возрастает. Эта сумма соответствует диагоналям матрицы. Значит будем рассматривать ячейки в порядке принадлежности их диагоналям. Или просто напишем рекурсию с запоминанием. Приведу код для второго случая:

    Ответом является dyn[n-1][m-1]

  6. Разбор. D. Стоимость маршрута

    Главное — обработать матрицу в правильном направлении — снизу вверх и слева направо. Основная формула динамики напрашивается сама собой:
    dyn[i][j] = min(dyn[i+1][j], dyn[i][j-1], dyn[i+1][j-1]) + inp[i][j];
    Если нужно написать подробнее, сообщите мне.

  7. Разбор. E. Спуск с горы

    Брат-близнец предыдущей задачи, только максимум вместо минимума и 2 направления вместо трех:
    dyn[i][j] = max(dyn[i-1][j-1], dyn[i-1][j]) + inp[i][j];
    Не забудем добавить фиктивные ячейки с минус бесконечностями по краям, чтобы не запариваться с обработкой выхода за границу.

  8. Разбор. F. Ядра

    Задача-мультирюкзак. Сначала посчитаем все возможные размеры пирамид линейной динамикой. Их будет $O(\sqrt[3]{m})$, где $m$ — максимально возможное значение $m_i$, что нас вполне устраивает. Сохраним их в массив sizes. Динамикой будем считать для текущего размера минимальное количество пирамид, необходимых для его получения. Для начала заполним основной массив динамики бесконечностями. База динамики: 0 ядер можно получить из 0 пирамид. Далее будем для каждой пирамиды пытаться прибавить ее к каждому уже полученном размеру и релаксировать ответ для нового размера.

    Здесь мы пользуемся тем, что каждая пирамида может быть добавлена сколько угодно раз, поэтому дальнейшие вычисления в цикле по j используют результаты предыдущих вычислений. Если бы все пирамиды должны были быть различными, то достаточно было бы цикл по j развернуть в обратном направлении.
    Сложность алгоритма $O(m \cdot \sqrt[3]{m})$

  9. Разбор. G. Длиннейший путь

    Задача является усложненной версией задачи про коня. И в обоих случаях имеем ациклический граф переходов, а значит можем решить задачу перебором с запоминаниями (по факту это DFS). Пусть мы храним граф g списками смежных вершин. Тогда для каждой вершины ответ 0, если она никуда не ведет и максимум среди ответов для ее детей + 1, если она ведет хоть куда-то. Чтобы не обрабатывать вершину дважды, будем запоминать результаты предыдущих запусков для каждой вершины.

    Поскольку по каждому ребру мы пройдемся ровно 1 раз, сложность алгоритма $O(m)$.

  10. Разбор. H. Мирные множества

    Будем добавлять во множества числа по порядку от меньшего к большему. Чтобы знать, можно ли добавить во множество $S$ число $x$, нам достаточно знать 2 значения: максимальное значение в $S$ — $max(S)$, чтобы выполнялось $max(S) \leq 2 \cdot x$ и значение силы множества $S$ — $F(S)$, чтобы выполнялось $F(S) + x \leq n$, ведь нас не интересуют множества с силой больше $n$. Зададим эти значения в качестве параметров квадратной динамики dyn[i][j]. $i = F(S)$, $j = max(S)$. И будем добавлять во множество все такие числа $k$: $2 \cdot j \leq k \leq n — i$.

    Сложность алгоритма $O(n^3)$, но за счет мультипликативной константы, сильно меньшей 1, должно заходить. Если нет, обращайтесь, будем думать.

  11. Разбор. I. Рюкзак

    Будем рассматривать слитки по порядку и выбирать: добавить текущий слиток или выбросить. Тогда нам достаточно знать, какие веса достижимы, если мы уже рассмотрели первые $i$ слитков. Будем поддерживать таблицу bool dyn[i][j], $i$ — количество рассмотренных слитков, $j$ — достигнутый вес. Тогда, заполнив изначально всю таблицу значениями false, и положив, что с 0 слитков достижим вес 0 ( dyn[0][0] = true;), будем для каждого множества пытаться добавлять или не добавлять текущий слиток.

    В конце найдем в n-ой строке максимальный достигнутый вес. Это и будет ответ. Заметим, что нас не интересуют веса, большие вместимости рюкзака, поэтому достаточно поддерживать матрицу $301 \times 10001$. Сложность алгоритма $O(s \cdot n)$.

  12. Разбор. J. Плохая строка

    Будем строить строку, дописывая по одному символу в конец. Заметим, что символ ‘b’ мы можем добавлять только после символов ‘b’ и ‘c’, а остальные символы — после любого. Тогда назначим параметрами динамики длину строки и последний символ (0, 1, 2 вместо ‘a’, ‘b’, ‘c’), а значением динамики — количество таких строк. Переходы:

    Можем оставить решение в таком виде.
    Или заметим, что dyn[i][2] полностью дублирует значение dyn[i][0]. Избавимся от лишнего. Тогда получим такие переходы:

    Сложность алгоритма $O(n)$.

Добавить комментарий