Що це за граф. «Вісімка» — це два цикли, що мають одну спільну вершину (перехрестя). Якщо виписати ліхтарі в рядок у порядку виводу
то сусідство в рядку дає майже всі потрібні обмеження. Бракує лише двох: перехрестя також сусідить із b_1 (замикає верхню петлю) та з d_y (замикає нижню). Отже задача звучить так:
розставити ліхтарів у рядок так, щоб сусіди різнилися, і вибрати позицію , колір якої відрізняється ще й від обох кінців рядка; при цьому по обидва боки від має лишитися щонайменше по два ліхтарі.
Коли відповідь існує. Розглянемо окремий цикл довжини : колір може зустрічатися в ньому щонайбільше разів (інакше два однакові неминуче стануть поруч). Наші цикли мають довжини x+1 і y+1, а x + y + 1 = n, тож найбільша кількість однакових ліхтарів, яку взагалі можна вмістити, дорівнює
Максимум досягається, коли обидві довжини парні (для непарного : x = 3, y = n-4) або одна парна, друга ні (для парного : x = 2, y = n-3). Звідси критерій:
k = 1 — відповіді немає ніколи;
k = 2 — обидва цикли мусять бути парними, тому кольори строго чергуються, і виходить \bigl| \mathrm{cnt}_1 - \mathrm{cnt}_2 \bigr| = 1; крім того потрібно n \ge 7 (при n = 5 обидві петлі — трикутники);
k \ge 3 — відповідь є тоді й лише тоді, коли \max_i \mathrm{cnt}_i \le \lceil n/2 \rceil, з єдиним винятком n = 5: там x = y = 2 вимушено, обидві петлі — трикутники, тож жоден колір не може траплятися більше двох разів.
Побудова для k = 2. Нехай — частіший колір, — рідший. Беремо x = 3, y = n - 4 і виводимо
Обидві петлі парної довжини, кольори в них чергуються, а перехрестя отримує рідший колір — рівно так і виходить різниця в одиницю.
Побудова для k \ge 3. Відкладемо на перехрестя один ліхтар найрідшого кольору — саме йому найлегше відрізнятися від обох кінців рядка. Решту розставляємо класичною жадібністю «переставити рядок без сусідніх однакових»: тримаємо кольори в купі за спаданням залишку і щоразу ставимо найчисленніший із тих, що не дорівнює попередньому. Ця жадібність успішна саме за умови \max \mathrm{cnt} \le \lceil n/2 \rceil; якщо на якомусь кроці залишився лише один колір, а ліхтарів більше одного, — відповіді немає.
Лишається розрізати рядок. Шукаємо входження кольору перехрестя на позиції з 3 \le \mathrm{pos} \le n-2: тоді верхня гілка — перші \mathrm{pos}-1 ліхтарів, нижня — останні n - \mathrm{pos}, обидві завдовжки не менше двох. Оскільки жадібність ставить на початок найчисленніші кольори, найрідший колір туди не потрапляє; окремо варто підстрахуватися лише тоді, коли найрідший колір трапляється рівно один раз — у цьому випадку спершу примусово поставте на перші дві позиції два найчисленніші кольори, і єдине входження гарантовано опиниться далі.
Складність — \mathcal{O}(n \log k) через купу (або \mathcal{O}(n + k), якщо розкладати кольори по кошиках).