Давно не было решений на С++. Сегодня разберём непростую задачу на динамическое программирование по подмножествам, которую на Python затолкать в ограничения очень сложно. Читаем условие:
Почти всегда, когда в задаче есть перебор перестановок, можно решение за O(N!) заменить решением за O(N * 2^N), используя динамическое программирование по подмножествам. Это всё ещё экспоненциальное решение, но константа сильно меньше.
В нашем случае, если решать задачу в лоб, то надо каждую перестановку ещё проверять на удовлетворение условий К-перестановки. То есть решение будет за O(N * N!). Значит, преобразовав к динамике, получим решение за O(N^2 * 2^N).
Динамика по подмножествам подразумевает вычисление ответа для всех подмножеств в порядке их увеличения. Например, есть числа 3, 6, 8. Сначала вычисляем ответ для множеств {3}, {6}, {8}. Затем уже можем вычислить для множеств {3, 6}, {3, 8}, {6, 8}, используя результаты одноэлементных множеств. И в самом конце - для {3, 6, 8}. Получаем итоговый ответ.
Однако в этой задаче дополнительная сложность - надо вывести определённую перестановку, а не просто посчитать их количество. Поэтому подмножеств недостаточно для состояния динамики. Вторым параметром будет первый элемент перестановки. То есть будем вычислять количество К-перестановок, начинающихся с X и состоящих из множества чисел A.
Давайте писать решение маленькими частями. Для начала определим используемые библиотеки, для простоты переопределим тип данных и заведём массив для результатов динамического программирования:
Также напишем функцию, которая вычисляет наибольший общий делитель:
Можно приступать к основному решению. Считаем данные и сразу отсортируем входной массив. Это нам пригодится, так как нам нужна последовательность в лексикографическом порядке:
Заведём булевский массив can, в котором для каждой пары элементов будем хранить возможность следования второго после первого. В этой задаче это отношение симметричное и вычисляется через наибольший общий делитель:
Но в общем случае, массив может иметь произвольную структуру. Благодаря такой архитектуре, это решение можно будет переиспользовать в подобных задачах с минимальными исправлениями.
Самая сложная часть решения - перебор подмножеств и вычисление значений ДП. Заметим, что множества удобно хранить в битовом массиве, где True означает, что этот элемент берём. А для удобства перебора битовый массив можно заменить числом и определять взятые элементы по его двоичной записи. Так число 5 будет означать, что берём первый и третий элементы (5 в двоичной системе счисления запишется как 101).
Заметим, что перебор подмножеств в порядке следования натуральных чисел будет отличаться от приведённого выше:
- {3} (число 1 = 001)
- {6} (число 2 = 010)
- {3, 6} (число 3 = 011)
- {8} (число 4 = 100)
- {3, 8} (число 5 = 101)
- {6, 8} (число 6 = 110)
- {3, 6, 8} (число 7 = 111)
При этом последовательность подмножеств будет корректной, так как для каждого множества все его подмножества соответствуют меньшим числам, то есть ответ для них уже вычислен.
Напишем заполнение массива dp:
В этом куске активно используются битовые операции, чтобы определять вхождение элементов во множество.
В цикле в строках 30-39 перебираем, каким мог бы быть первый элемент перестановки. И в условии на строке 31 проверяем, что он входит в подмножество.
А в цикле на строках 36-38 перебираем все возможные вторые элементы перестановки. Проверяем, что этот элемент тоже входит в подмножество, а также проверяем условие can, что этот элемент может идти следом за i-ым.
Условие в строках 32-35 выполняет роль базы динамики - для множеств из одного элемента записываем 1 (ровно одну перестановку можно получить).
Теперь можно посчитать количество К-перестановок, и если их меньше M, то выведем -1:
Более сложный кусок - получение итоговой перестановки. Как обычно в динамике, это выполняется движением с конца. Берём подмножество из всех входных чисел и перебираем первое число перестановки, считая, сколько таких перестановок. Как только сумма становится больше M, это означает, что первый элемент найден.
Выкидываем найденный элемент из подмножества, из M вычитаем количество перестановок, которые начинаются на числа меньше найденного. И повторяем процедуру:
Код получился размашистый. Рекомендую воспроизвести пример решения на входных данных из условия задачи на листочке:
Получили решение сложной задачи. Здесь и сам алгоритм не простой - динамическое программирование по подмножествам - тема не из лёгких. И реализация тоже нетривиальная (как это часто бывает в динамике), нам пришлось вычислять наибольшие общие делители, работать с битовыми масками и не забыть про переполнение типа.
Предыдущий выпуск: Задача 536. Числа - 2
Задонатить автору на бусти.
Я очень хочу, чтобы мои советы были полезны вам, а для того, чтобы быстрее всех получать новые статьи можно подписаться на мой канал.