9.9. Подсказки к задачам

Задача 9.2: За типа \(O(NS^2)\) решается легко: как и раньше, для каждого \((i,j)\) определим, можно ли набрать сумму \(j\) с помощью первых \(i\) монет. Для этого переберём, сколько раз в решение будет входить \(i\)-ая монета, и для каждого варианта понятно, как сводится к уже насчитанным решениям с \(i-1\). Осталось придумать, как ускорить это решение до \(O(NS)\).

Задача 9.3: Почти всегда дополнительные условия вида «если есть несколько решений, выведите то, в котором минимально/максимально что-то ещё» учитываются легко: кроме основного массива, насчитываемого динамикой, заведём ещё один массив, в котором будем хранить это самое оптимальное «что-то ещё», и в основной динамике, когда есть выбор, будем выбирать подходящий вариант с учётом этого второго массива.

В данном случае заведём ещё массив \(min\), и, если сумму \(j\) можно набрать с помощью первых \(i\) типов монет, то в \(min[i,j]\) будем хранить минимальное количество монет, которыми можно её набрать. Додумайте, а также придумайте, как обойтись только одним массивом.

Задача 9.5: Идея: будем не просто для каждого \(i\) и \(j\) решать задачу дойти до \((i,j)\), а: для каждого \(i\), \(j\), \(a\) и \(b\) (здесь \(i\) и \(j\) — координаты клетки, а \(a\) и \(b\) каждое может принимать лишь два значения, условно обозначающие ход вверх и вправо) будем искать оптимальный путь до клетки \((i,j)\) среди всех путей, у которых последний ход \(b\), а предпоследний — \(a\) (т.е., например, как оптимальнее всего дойти до \((10,15)\) так, чтобы в конце сходить вправо и потом вверх?) Додумайте, как тут будет производиться сведение к более мелким подзадачам

Задача 9.6: Решается в точности аналогично простой задаче про черепашку.

Задача 9.7: Если ответ ещё не очевиден, то попробуйте посмотреть на ответ на предыдущую задачу и понять, что тут будет не так, если условия не выполняются. Попробуйте представить себе, какой будет граф подзадач, если эти условия не выполняются.

Задача 9.9: Может быть, ответ вам сразу очевиден. Может быть, наоборот, вопрос обескураживает. В последнем случае попробуйте перенести идею решения с задачи про монеты на задачу про черепашку и подумайте, что тут не так.

Задача 9.16: Конечно, будет удобно переписать динамику, аналогично выводу первого в лексикографическом порядке решения, чтобы вообще было удобно работать с лексикографическом порядке, дальше все просто по стандартному сценарию.

Можно не переписывать динамику, а «передумать» её, и не переписывать, но будет некоторое несоответствие между «текущей позицией» черепашки и координатами в массиве \(ans\) (додумайте :) )

Задача 9.18: Сначала сделайте задачи про вывод первого пути и вывод k-го пути, после этого эта задача сложностей составлять не должна.

Задача 9.20: Удобнее «развернуть» динамику, как мы обсуждали в разделе про вывод лексикографически первого или \(k\)-го решения.

Задача 9.21: Идея простая: давайте для каждого момента времени \(t\) посчитаем, сколько максимум гвоздиков может забить папа Карло к моменту времени \(t\). Как решить подзадачу? Наученные опытом прошлых задач (и задачи про монеты с повтором, и концом раздела ДП на подотрезках, если вы до туда добрались, и другими задачами), мы не будем перебирать, когда папа Карло закончит забивать последний гвоздь, а просто рассмотрим два варианта: либо папа Карло закончил забивать последний гвоздь в момент \(t\), либо раньше — и тогда от \(t-1\) до \(t\) у него был перерывчик.

Все просто, но рассмотреть первый вариант нетривиально: когда папа Карло мог начать забивать гвоздик, если закончил в момент \(t\)? Перебирать все вообще моменты времени долго, и сложность получится квадратичной, но можно проще, воспользовавшись идеей динамики с просмотром вперёд.

Задача 9.22: В принципе, задача была бы совсем простая, если бы не требование про ведущие нули. Но, раз ведущие нули запрещены, то приходится немного повозиться. В принципе, можно так все и сделать, но упрощает реализацию либо использование динамики с просмотром вперёд, либо «обращение» динамики, как в задаче про Буратино.

Задача 9.23: Конечно, тут все просто, но надо бы это облечь в строгую форму. С ходу сказать, что это очевидно, нельзя. Например, почему, если \(s_1[i]=s_2[j]\), то мы оставляем обе буквы? Почему не может быть так, что одну выкидываем?

Задача 9.25: Хочется сразу обратить динамику, чтобы выводить решение с начала в конец. Но это не сильно помогает. В случае \(s_1[i]\neq s_2[j]\) нужно будет выбрать, какой из двух вариантов выводить, и если они одинаковой длины, то придётся сравнивать их лексикографически, что очень нетривиально: мало того, что сложно понять, на какую букву начинается решение, так ведь ещё эти буквы могут оказаться одинаковыми, и надо будет смотреть вторую букву и т.д.

В общем, я не знаю, как тут по стандартному шаблону выводить первое в лексикографическом порядке решение, поэтому придётся привлекать тяжёлую артиллерию — учитывать необходимость вывода лексикографически первого решения прямо в динамике. Подумайте. Кстати, сложность решения тут повысится до \(O(N^3)\), и я не знаю, как её улучшить.

Задача 9.27: Аналогия тут полная, только решение будет кубическое: для каждых \((i,j,k)\) найдём наибольшую общую подпоследовательность понятно чего.

Задача 9.28: Тут, кстати, аналогия с наибольшей общей подпоследовательностью (и с соответствующей задачей) проявляется наиболее ярко.

Задача 9.30: Это — как раз пример на не совсем обычную процедуру \(out\).

Задача 9.31: Тут все аналогично задаче про первую в лексикографическим порядке общую подпоследовательность. Правда, тут скорее дело даже не в аналогии между задачами, а вообще в общности методов «тяжёлой артиллерии» для учёта таких требований.

Задача 9.32: Эта задача вам ничего из того, что мы тут разбирали, не напоминает? Да и не забудьте тему раздела — динамика по полной сумме. Правда, тут «полных сумм» две — вес и стоимость, но, я думаю, несложно догадаться, по какой из них надо динамику.

Задача 9.33: Вам может оказаться полезным использовать массив \(from\).

Задача 9.34: Будем считать, что дерево задано «хорошо», т.е. массивом \(p\). Для каждого поддерева найдём размер максимального паросочетания в нем… Правда, если подумать, то это оказывается не очень тривиально; во всяком случае, я с ходу не вижу, как это просто решить. Но подумайте. Полезно будет решать две задачи: максимальное паросочетание в поддереве с корнем в \(u\) при условии, что сама вершина \(u\) входит в паросочетание, и при условии, что не входит. Написать рекуррентное соотношение несложно, но реализовать ДП с просмотром вперёд сложнее.

Задача 9.36: На первый взгляд может показаться, что здесь граф неациклический: ведь второй игрок может увеличивать количество камешков в куче. Но на самом деле, т.к. игроки ходят по очереди, и первый всегда берет больше, чем второй кладёт, то ясно, что на самом деле граф ациклический, только под позицией надо понимать пару \((i,j)\), где \(i\) — количество камешков в группе, а \(j\) — тот, кто сейчас ходит (т.е. \(j\) равно 1 или 2).

Задача 9.37: Совершенно стандартно: пишем процедуру \(out(i)\), которая будет выводить решение для множества \(i\). Может быть, на первый взгляд хочется в процедуре \(out\) заново перебирать все варианты, как в основном коде динамики — но нет, этого не надо. Достаточно сделать массив \(from\), в котором хранить, где мы нашли наилучшее решение для данного \(i\).

Ещё может быть полезным сделать массив \(first\), и в \(first[i]\) хранить номер первой вершины, лежащей в множестве \(i\) (т.е. то \(j\), которое использовалось в основном цикле динамики), чтобы не делать заново цикл по \(j\).

Задача 9.38: Подзадачей у нас будет «сколько существует \(k\)-перестановок на множестве \(i\), начинающихся на число №\(j\)», т.е. параметры динамики — \(i\) и \(j\). Дальше, я думаю, идеологически все просто, но технически надо повозиться.

Во-первых, конечно, надо будет отсортировать те числа, которые вам даны. Во-вторых, тут будет нетривиальная инициализация динамики — я не смог придумать, как бы обойтись инициализацией только пустого множества, приходится в качестве «базы динамики» рассматривать все множества размера 1. В-третьих, удобно будет ввести ещё одно число, которое может соседствовать с любым данным числом, чтобы для получения общего количества \(k\)-перестановок не суммировать в отдельном цикле \(ans[i,j]\) по всем \(j\), а сразу получить ответ в соответствующем элементе \(ans\) (если сейчас не понятно, то пока забейте, потом посмотрите решение).

Задача 9.42: а) Тут есть два решения.

Одно основано на понятии баланса, т.е. разницы между числом открывающих и закрывающих скобок в некоторой строке. Строка является правильной скобочной последовательностью, если баланс любого её начала \(\geq 0\), а баланс всей строки равен нулю. Ну так давайте для каждого \(i\) и \(j\) посчитаем, сколько есть строк длины \(i\) из символов ’(’ и ’)’ с балансом \(j\).

Второе вариант — правильная с.п. начинается, конечно, на открывающую скобку. Где будет парная к ней закрывающая? Пусть в позиции \(2k\) (позиция, очевидно, должна быть чётной), тогда очевидно, что между ними — любая правильная с.п. из \(k-1\) пары скобок, а после — любая правильная с.п. из \(N-k\) пар. Дальше просто.

Подумайте, можно ли и как эти решения обобщить на пункт б).

Задача 9.43: ДП по профилю.

Задача 9.44: Двумерное ДП. Придумайте решение за \(O(NM)\).