Автор задачи и разработчик: Даниил Орешников
Упростим формулировку задачи: даны $$$n + 1$$$ стек, вмещающие не более двух элементов, в них лежат $$$n$$$ пар элементов с номерами от $$$1$$$ до $$$n$$$; требуется перекладываниями верхних элементов из стеков добиться того, чтобы парные элементы лежали в одном стеке.
Заметим, что если в каждой паре один элемент лежит снизу какого-то стека, а другой — сверху, то можно справиться с задачей следующим образом. Выберем первый стек, переложим верхний элемент из него в «запасной» пустой. Пара к тому элементу, который остался внизу первого стека, лежит где-то наверху в другом — переложим его в первый. Продолжим то же самое для стека, из которого только что переложили верхний, и так далее, пока не найдется пара к самому первому отложенному элементу.
На упорядочивание каждого такого «цикла» размера $$$k$$$ требуется $$$k + 1$$$ действие, и всего есть не более $$$\frac{n}{2}$$$ таких циклов, поэтому хватит $$$\frac{3}{2}n$$$ действий.
Теперь обобщим это решение на случай, когда есть пары с двумя «верхними» или двумя «нижними» элементами (по их исходному расположению в стеках). Рассмотрим произвольный стек, пусть в нем лежат элементы $$$3$$$ (сверху) и $$$4$$$ (снизу). Посмотрим, лежит ли где-то $$$3$$$ снизу — если да, то пусть, не теряя общности, верхний элемент в его стеке равен $$$2$$$, продолжим то же рассуждение для $$$2$$$, и аналогично продолжим для $$$4$$$ в другую сторону. Рано или поздно, мы остановимся, либо замкнувшись в цикл, либо встретив с обеих сторон элемент, чья пара находится на той же глубине в другом стеке: $$$$$$\begin{aligned} &[x, {\color{red} 1}\\ &[2, {\color{red} 1}\\ &[3, 2\\ &[4, 3\\ &[{\color{red} 5}, 4\\ &[{\color{red} 5}, y \end{aligned}$$$$$$
В таком случае выложим два парных верхних элемента ($$$1$$$ и $$$1$$$) в пустой стек, переместим $$$2$$$, $$$3$$$, $$$4$$$ по циклу, как в предыдущем случае, дальше переложим $$$y$$$ на $$$x$$$, и, наконец, переместим $$$5$$$. В данном случае мы получили $$$k - 1$$$ новых парных стеков, потратив $$$k + 1$$$ действие, где $$$k$$$ — длина такой цепочки. Поскольку цепочки имеют длину хотя бы $$$3$$$, то если все стеки разбиваются на циклы или цепочки, нам хватит $$$2n$$$ действий даже с запасом.
Так же стоит аккуратно обрабатывать случай $$$x = y$$$, в котором цепочка зацикливается, и, в частности, случай двух одинаковых стеков, образующих две пары.
Для реализации этого алгоритма достаточно в явном виде хранить для каждого номера пары две позиции элементов из нее, а также сами стеки. При перемещениях можно просто изменять состояние стеком и обновлять информацию о том, где какой элемент находится. Так же следует поддерживать номер вспомогательного пустого стека, потому что он периодически меняется. Время работы решения — $$$\mathcal{O}(n)$$$.