Козак Вус та залізнична дорога

Автор та розробник: Андрій Романов

Цю задачу можна вирішувати багатьма способами, я наведу один з них.

Блок 1. Можемо зробити повний перебір по всіх розстановках ліхтарів і перевірити, чи хоча б одна з них задовольняє умові задачі. Складність такого розв'язку $$$O(n! \cdot n)$$$.

Блок 2. Для зручності будемо називати ті $$$n/2$$$ ліхтарі, що мають один і той самий колір червоними. Розставимо $$$n/2-1$$$ червоні ліхтарі на верхню гілку і між ними поставимо $$$n/2-1$$$ не червоних ліхтарів, в тому числі один з них на перехресті. В нас лишився один червоний і один не червоний ліхтар(назвемо його особливим). Якщо $$$k \geq 3$$$, то за потреби замінимо особливий ліхтар на не червоний такий, колір якого відрізняється від кольору ліхтаря на перехресті та два ліхтарі, що в нас лишилися поставимо на нижню гілку. Якщо ж $$$k=2$$$, то обов'язково кількість ліхтарів різних кольорів буде рівна як на верхній, так і на нижній гілках, і через те, що ліхтар на перехресті враховується двічі, то кількості ліхтарів різних кольорів будуть відрізнятися. Отже, при $$$k=2$$$ відповідь в цьому блоці завжди $$$-1$$$.

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

Блок 4. Як і в першому блоці можемо перебрати всі можливі розстановки. Складність такого розв'язку $$$O(2^n \cdot n)$$$.

Блок 5. Як на верхній, так і на нижній гілці кількість одиниць і двійок буде однаковою, але одиниця/двійка на перехресті буде врахована два рази, а отже кількість одиниць/двійок на один більша за кількість двійок/одиниць. Отже, якщо $$$n$$$ парне або кількості одиниць і двійок відрізняються хоча б на $$$2$$$, то відповідь $$$-1$$$. Інакше розставимо $$$(n+1)/2$$$ одиничок і $$$(n-1)/2$$$ двійок. Випадок, коли двійок більше розглядається аналогічно. Якщо n=5, то нам не вдасться розставити ці ліхтарі вздовж залізничної дороги, адже завжди знайдуться два сусідні ліхтарі одного кольору. Інакше поставимо ліхтар $$$2$$$ на перехрестя. Розставимо $$$n-4$$$ ліхтарі в порядку $$$1 2 1 \dots 2 1$$$ на верхній гілці. Тепер розставимо $$$3$$$ ліхтарі $$$1 2 1$$$ на нижній гілці. Задане розташування задовольняє умові задачі.

Блок 6. Назвемо ліхтар максимальним, якщо ліхтарів його кольору найбільше серед інших, мінімальним, якщо ліхтарів його кольору найменше серед інших. На обидвох гілках максимальних ліхтарів не може бути більше ніж сумарно ліхтарів інших кольорів, бо інакше б якісь два максимальні ліхтарі стояли поруч. При цьому перехрестя враховувалося два рази, тому якщо на перехресті стоїть не максимальний ліхтар, то кількість максимальних ліхтарів може бути більшим на $$$1$$$ за кількість ліхтарів всіх інших кольорів. Отже, якщо кількість максимальних ліхтарів хоча б на $$$2$$$ більша за сумарну кількість всіх інших ліхтарів, то відповідь $$$-1$$$, інакше розв'язок існує.

Поставимо на перехрестя мінімальний ліхтар. Тепер будемо виставляти на верхню гілку максимальний і мінімальний ліхтарі на цей час по черзі. Будемо продовжувати цей процес доки в нас не залишаться ліхтарі лише одного кольору. З обмежень, які ми розглянули в минулому абзаці в нас може залишитися не більше двох ліхтарів одного кольору. Можна показати, що останній ліхтар на верхній гілці відмінного кольору від ліхтаря на перехресті, адже такі ліхтарі були використані в першу чергу, а $$$k \geq 3$$$ (при $$$k=1$$$ відповідь $$$-1$$$). Якщо в нас на руках два ліхтарі одного кольору, то поставимо їх на нижню гілку і між ними поставимо останній ліхтар з верхньої гілки. Якщо в нас на руках один ліхтар, то поставимо його на нижню гілку разом з останнім ліхтарем з верхньої гілки. Якщо в нас на руках не лишилося жодного ліхтаря, то переставимо останні два ліхтарі з верхньої гілки на нижню гілку. Передостанній ліхтар був максимальним, отже його колір точно відмінний від ліхтаря на перехресті. Таким чином ми отримаємо розстановку, що задовольняє умові задачі. Максимальний і мінімальний елемент можна шукати проходом по масиву. Складність алгоритму $$$O(n^2)$$$.

Блок 7. Об'єднуємо $$$5$$$ і $$$6$$$ блоки разом.

Блок 8. Будемо підтримувати сет, де будемо зберігати пари (поточна кількість ліхтарів кольору $$$x$$$, $$$x$$$). Таким чином зможемо шукати максимальний і мінімальний елементи за $$$\log(n)$$$. Загальна асимптотика $$$O(n \log n)$$$.