Editorial

Якщо всі кольори однакові, то неможливо посортувати, крім випадку, коли всі книги зразу правильно стоять.

Підзадача 1. Навчимося розв'язувати задачу за $3n$ операцій. Зробимо функцію, яка міняє місцями будь-які $2$ книги. Якщо вони різного кольору, то просто за $1$ операцію міняємо їх місцями. Якщо однакового, то зробимо 3 операції, використовуючи ще одну книгу іншого кольору, ніж ці дві. Далі просто зліва направо виставляємо книги на свої місця.

Цей розв'язок можна оптимізувати до $2n$ операцій. Будемо виставляти книги на свої місця по черзі. Якщо нам потрібно поставити книгу на місце, а там стоїть книга такого ж кольору, то візьмемо книгу іншого кольору, яка ще не на своєму місці, і за допомогою її поставимо за 2 операції початкову на своє місце. Потрібно, щоб завжди була книга іншого кольору, яка ще не на своєму місці. Для цього оберемо правильний порядок, у якому виставляти книги на свої місця. Як варіант, будемо ставити книги на свої місця так, щоб завжди була хоча б одна книга кожного кольору не на своєму місці. Коли вже кожного кольору залишиться по одному, доставимо їх. Можливо і далі оптимізувати цей розв'язок.

Підзадача 2. Розіб'ємо перестановку на цикли. Нехай спочатку є $k$ циклів. За одну операцію можливо збільшити кількість циклів максимум на $1$. Нам потрібно досягти стану, коли всі елементи лежать в окремих циклах. Якщо ми міняємо $2$ книги, які лежать в одному циклі, то цей цикл розіб'ється на $2$. Тому будемо міняти книги так, щоб кожного разу брати $2$ елементи з одного циклу і за $n-k$ операцій вийде посортувати.

Підзадача 3. Розіб'ємо перестановки на цикли. Якщо в циклі довжини $l$ є хоча б $2$ різні кольори, то його можна розв'язати за $l-1$ операцію. Розв'язати означає поставити всі книги з цього циклу на свої місця. Для цього ми будемо виставляти по одному елементу на своє місце за одну операцію (це можна зробити, якщо $2$ сусідні за циклом книги різного кольору). Але не можна, щоб залишилися книги тільки одного кольору, для цього потрібно зафіксувати порядок, схожий най той, що в підзадачі $1$.

Тепер залишилися цикли, які складаються тільки з книг однакового кольору. Назвемо такі цикли поганими. Зауважимо, що якщо міняти місцями $2$ елементи з різних циклів, то ці цикли об'єднуються. Зрозуміло, що кожен поганий цикл потрібно спочатку об'єднати з якимось іншим. Причому кількість об'єднань повинна бути мінімальна, бо кількість операцій буде рівна $n$ -кількість_циклів+2*кількість_об'єднань. Ми можемо об'єднати $2$ погані цикли різних кольорів, і тоді цей цикл стане хорошим. Тому нам вигідно розбити погані цикли на якнайбільше пар, де в кожній парі цикли різних кольорів. Нехай є $c_i$ поганих циклів кольору і. Вигідно брати 2 максимальні $c_i$ і з відповідних циклів утворювати пару. Цей розв'язок реалізовується за $O(n\log n)$.