Задача всегда имеет решение. Достаточно с нужной стороны подогнать колечко N к колечку N-1, а дальше действовать рекурсивно, считая, что колечки N и N-1 склеены. Такое решение идейно простое, но не самое легкое для реализации, так как при протаскивании "склеенного колечка" необходимо делать сразу несколько перемещений.

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

Решение заключается в том, что мы находим пару (x, y) соседних правильно упорядоченных колечек (x < y) таких, что их можно протащить друг через друга (|y-x| > 1), т.е. y-x > 1. Перетаскиваем колечки, ищем новую пару и так далее пока не получим полное упорядочивание колечек. Данное решение очень легко запрограммировать, но совершенно не понятно, почему оно всегда выдает правильный ответ.

Чтобы это понять, рассмотрим частный случай алгоритма: берем колечко с номером 1 и перемещаем его по часовой стрелке до тех пор, пока это возможно, т.е. пока не встретим колечко с номером 2. Затем аналогично перемещаем колечко с номером два, и так далее. В какой-то момент мы дойдем до последнего колечка. После этого повторяем проделанные операции заново и вновь пытаемся переместить колечко с номером 1. Интуитивно понятно, что в результате таких операций происходит постепенное упорядочивание колечек. Когда все колечки будут упорядочены по часовой стрелке, алгоритм завершит свое выполнение, так как ни одно из них невозможно будет переместить.

Докажем корректность работы алгоритма. Рассмотрим функцию Dist(x, y), которая возвращает расстояние от колечка x до колечка y, если двигаться по часовой стрелке. Дополнительно рассмотрим сумму S = 1xDist(1, 2)+ 2xDist(2, 3)+...+ nxDist(n, 1). Очевидно, что при смене колечек x и y местами в сумме S изменяются только слагаемые Dist(x, x+1) и Dist(y, y+1). Первое слагаемое при такой транспозиции увеличивается на 1, а второе - уменьшается на 1, значит, а вся сумма изменяется на величину ∆S = x-y. Учитывая, что x < y, получаем, что в результате перестановки колечек x и y сумма S уменьшается, а так как S все время остается положительным, то наш алгоритм рано или поздно закончит работу. Для завершения необходимо заметить, что в любой позиции, кроме правильного упорядочивания, существует "правильная" пара колечек, которые алгоритм должен поменять местами. Значит, после завершения работы алгоритма получится расстановка 1, 2, ..., N.

Можно доказать, что оба алгоритма выдают минимально возможное количество перестановок и в случае расположения колечек в обратном порядке общее количество транспозиций будет (N-2)(N-1)N/6. Получается, что верное решение задачи имеет кубическое время выполнения и линейный расход по памяти, а максимальное количество перестановок получается на тесте 50, 49, ..., 1 и равно 19600.

Правильное решение набирает 100 баллов.

При небольших значениях N (N ≤ 11) верный ответ можно получить с помощью такого алгоритма: создаем граф, вершинами которого являются всевозможные конфигурации ожерелья. Затем при помощи поиска в ширину находим нужную последовательность транспозиций. Такое решение набирало 40-50 баллов.

Помимо этого оценивались решения, которые разбирали случаи маленьких значений N, прямой и обратный порядок расположения колечек и оценивалось примерно в 30 баллов. Решения, которые выдавали только 0 и -1 или проходили только тривиальные тесты на прямой порядок оценивались в 0 баллов.

Учитывая, что информация о номерах колечек хранится в массиве, можно было допустить ряд ошибок, связанных с тем, что массив - линейный объект, а ожерелье замкнуто и представляет циклическую структуру. Естественно такие решения проходили не все тесты и за счет ошибок реализации набирали меньшее количество баллов.