Еще более защищенная тюрьма

Автор задачи и разработчик: Даниил Орешников

После нажатия на сектор номер $$$i$$$ вся последовательность чисел — это циклический сдвиг исходной последовательности на $$$a_i$$$ против часовой стрелки, из которого затем выкинут элемент $$$a_i$$$.

Посмотрим, как решалась бы задача, если бы элементы не убирались из рассмотрения. Тогда нам бы просто надо было научиться быстро сравнивать два циклических сдвига, после чего найти минимальный из них с данными ограничениями можно как за линию, так и сделав полную сортировку всех циклических сдвигов, используя найденный компаратор. Для этого можно построить суффиксный массив, который позволит нам сравнивать циклические сдвиги за $$$\mathcal{O}(1)$$$.

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

Сравнивать две произвольные строки одинаковой длины можно, сохранив используемый при построении суффиксного массива массив классов для каждой итерации. После $$$i$$$-й итерации нам известен порядок на подстроках длины $$$2^i$$$, таким образом для сравнения двух подстрок длины $$$a$$$, достаточно посмотреть на их префиксы и суффиксы длины $$$2^{\lfloor\log_2a\rfloor}$$$ и сравнить их классы после $$$\lfloor\log_2a\rfloor$$$-й итерации.

Сделав константное число таких сравнений, мы можем получить результат сравнения двух ответов, получаемых выбором любых $$$i$$$-го и $$$j$$$-го секторов, а значит, опять же, за $$$\mathcal{O}(n)$$$ можно найти минимальный ответ. Суммарное время работы равно $$$\mathcal{O}(n \log n)$$$ на построение суффиксного массива.