Автор задачи и разработчик: Даниил Орешников
Задача может быть вкратце описана следующим образом: для каждого $$$i$$$ от $$$1$$$ до $$$n$$$ выбрать либо $$$p_i$$$, либо $$$(q \circ p)_i$$$, чтобы все выбранные числа были различны, и чтобы числа ни из какой пары ($$$a_t, b_t)$$$ не были выбраны для $$$i$$$ и $$$i + 1$$$.
Первая подгруппа решается полным перебором всех случаев. Достаточно просто посмотреть на то, какие комбинации могут получиться при тех или иных выборах, и для каждого проверить все необходимые условия. Вторая подгруппа аналогична, однако для ее решения уже не хватит только условных операторов, потребуется написать полный перебор всех вариантов выбора с проверкой условий за время $$$\mathcal{O}(2^n \cdot n)$$$.
Третья подгруппа гарантирует, что перестановка $$$p$$$ не двигает элементы, то есть для каждого $$$i$$$ можно выбрать либо $$$i$$$, либо $$$q_i$$$. Можно также заметить, что пятая группа полностью аналогична — для каждого $$$i$$$ можно выбрать либо $$$p_i$$$, либо $$$i$$$. Не теряя общности, расмотрим третью погруппу. Можно было заметить, что множество тех $$$i$$$, для которых выбрано не $$$i$$$, должно сохраняться при применении к нему перестановки $$$q$$$, значит должно состоять из одного или более циклов перестановки $$$q$$$. На таких циклах в качестве вершин можно построить граф, показывающий, можно или нет эти циклы выбрать вместе, после чего написать перебор с отсечением по времени.
Ограничения четвертой группы гарантируют только одно условие на ненахождение каких-то двух модулей рядом. Если в перестановке $$$p$$$ они уже не находятся рядом, достаточно просто выбрать ее. Иначе, надо рассмотреть три случая — когда вместо $$$q \circ p$$$ выбрано для $$$a_1$$$, для $$$b_1$$$ и для них обоих, и проверить, подходит ли хотя бы один.
Полное решение можно было получить, сведя задачу к 2-SAT. Заведем переменную $$$t_i$$$, которая принимает значение $$$\mathtt{true}$$$, когда выбрана $$$p_i$$$, и $$$\mathtt{false}$$$, когда выбрана $$$(q \circ p)_i$$$. Место, на котором окажется модуль $$$x$$$ при выборе $$$p$$$, обозначим $$$p^{-1}_x$$$, и аналогично $$$(qp)^{-1}_x$$$ для $$$q \circ p$$$.
Теперь для каждой пары $$$(a_i, b_i)$$$ переберем все возможные способы их расположения при выборе $$$p$$$ или $$$q \circ p$$$ (их всего четыре). Например, $$$x = p^{-1}_{a_i}$$$ и $$$y = (qp)^{-1}_{b_i}$$$. Если $$$|x - y| = 1$$$, то добавим импликации $$$t_x \to \lnot t_y$$$ и $$$t_y \to \lnot t_x$$$, так как эти два выбора не могут быть сделаны вместе. Так мы учтем все условия на соседние модули.
Теперь еще учтем условия вида $$$t_{p^{-1}_i} \to \lnot t_{(qp)^{-1}_i}$$$ и аналогичное ему обратное, $$$t_{(qp)^{-1}_i} \to \lnot t_{p^{-1}_i}$$$, что позволит гарантировать, что все конечное назначение тоже будет перестановкой (все модули будут различными, каждый — в своем слоте).
Всего мы получили $$$\mathcal{O}(n + m)$$$ условий, на которых мы можем запустить решатель 2-SAT через выделение компонент сильной связности за время $$$\mathcal{O}(n + m)$$$.