Розбір
Автор та розробник: Роман Білий
Якщо всі кольори однакові, то неможливо посортувати, крім випадку, коли всі книги зразу правильно стоять.
Підзадача 1
. Навчимося розв'язувати задачу за операцій. Зробимо функцію, яка міняє місцями будь-які книги. Якщо вони різного кольору, то просто за операцію міняємо їх місцями. Якщо однакового, то зробимо 3 операції, використовуючи ще одну книгу іншого кольору, ніж ці дві. Далі просто зліва направо виставляємо книги на свої місця.
Цей розв'язок можна оптимізувати до операцій. Будемо виставляти книги на свої місця по черзі. Якщо нам потрібно поставити книгу на місце, а там стоїть книга такого ж кольору, то візьмемо книгу іншого кольору, яка ще не на своєму місці, і за допомогою її поставимо за 2 операції початкову на своє місце. Потрібно, щоб завжди була книга іншого кольору, яка ще не на своєму місці. Для цього оберемо правильний порядок, у якому виставляти книги на свої місця. Як варіант, будемо ставити книги на свої місця так, щоб завжди була хоча б одна книга кожного кольору не на своєму місці. Коли вже кожного кольору залишиться по одному, доставимо їх. Можливо і далі оптимізувати цей розв'язок.
Підзадача 2
. Розіб'ємо перестановку на цикли. Нехай спочатку є циклів. За одну операцію можливо збільшити кількість циклів максимум на . Нам потрібно досягти стану, коли всі елементи лежать в окремих циклах. Якщо ми міняємо книги, які лежать в одному циклі, то цей цикл розіб'ється на . Тому будемо міняти книги так, щоб кожного разу брати елементи з одного циклу і за операцій вийде посортувати.
Підзадача 3
. Розіб'ємо перестановки на цикли. Якщо в циклі довжини є хоча б різні кольори, то його можна розв'язати за операцію. Розв'язати означає поставити всі книги з цього циклу на свої місця. Для цього ми будемо виставляти по одному елементу на своє місце за одну операцію (це можна зробити, якщо сусідні за циклом книги різного кольору). Але не можна, щоб залишилися книги тільки одного кольору, для цього потрібно зафіксувати порядок, схожий най той, що в підзадачі .
Тепер залишилися цикли, які складаються тільки з книг однакового кольору. Назвемо такі цикли поганими. Зауважимо, що якщо міняти місцями елементи з різних циклів, то ці цикли об'єднуються. Зрозуміло, що кожен поганий цикл потрібно спочатку об'єднати з якимось іншим. Причому кількість об'єднань повинна бути мінімальна, бо кількість операцій буде рівна -кількість_циклів+2*кількість_об'єднань. Ми можемо об'єднати погані цикли різних кольорів, і тоді цей цикл стане хорошим. Тому нам вигідно розбити погані цикли на якнайбільше пар, де в кожній парі цикли різних кольорів. Нехай є поганих циклів кольору і. Вигідно брати 2 максимальні і з відповідних циклів утворювати пару. Цей розв'язок реалізовується за .