Перестроения

Заметим, что для решения задачи достаточно получать из тождественной перестановки $$$\{1, 2, \ldots, n\}$$$ произвольную перестановку. Получение перестановки $$$b$$$ из перестановки $$$a$$$ эквивалентно получению перестановки $$$a^{-1}b$$$ из тождественной перестановки, где $$$a^{-1}$$$ — обратная к $$$a$$$ перестановка.

Пусть мы хотим получить из тождественной перестановки перестановку $$$p$$$. Будем решать задачу рекурсивно. Рассмотрим последнее перестроение, после которого мы получим перестановку $$$p$$$. Найдем решение, при котором в этом перестроении из ряда вышло $$$k = \lfloor \frac{n}{2} \rfloor$$$ человек. Очевидно, это люди с номерами $$$p_1, p_2, \ldots, p_k$$$, так как в конце именно они должны стоять в начале ряда. Разобьем всех людей на две группы: людей с номерами $$$p_1, p_2, \ldots, p_{k - 1}, p_k$$$ и людей с номерами $$$p_{k + 1}, p_{k + 2}, \ldots, p_{n - 1}, p_n$$$. Для решения задачи необходимо и достаточно, чтобы перед последним перестроением люди из первой группы стояли друг относительно друга в порядке $$$p_k, p_{k - 1}, \ldots, p_2, p_1$$$ (ведь при последнем перестроении их относительный порядок изменится на обратный), а люди из второй группы стояли друг относительно друга в порядке $$$p_{k + 1}, p_{k + 1}, \ldots, p_{n - 1}, p_n$$$. При этом относительный порядок людей из разных групп нам не важен.

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

Значит, задачу можно решать рекурсивно. Построим необходимые перестроения для каждой из групп, а после этого объединим пары перестроений внутри групп в перестроения всего ряда.

Мы свели задачу для перестановки размера $$$n$$$ к двум задачам для перестановок размера $$$\frac{n}{2}$$$ и одному дополнительному перестроению. Значит, общее количество перестроений для перестановки размера $$$n$$$ не превысит $$$\lceil \log_2{n} \rceil$$$. Этого хватает, чтобы уложиться в $$$15$$$ перестроений для перестановок размера не более $$$10\,000$$$.