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

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

Що це за граф. «Вісімка» — це два цикли, що мають одну спільну вершину (перехрестя). Якщо виписати ліхтарі в рядок у порядку виводу

b_1,\ b_2,\ \ldots,\ b_x,\ \underbrace{c}_{\text{перехрестя}},\ d_1,\ d_2,\ \ldots,\ d_y,

то сусідство в рядку дає майже всі потрібні обмеження. Бракує лише двох: перехрестя також сусідить із b_1 (замикає верхню петлю) та з d_y (замикає нижню). Отже задача звучить так:

розставити ліхтарів у рядок так, щоб сусіди різнилися, і вибрати позицію , колір якої відрізняється ще й від обох кінців рядка; при цьому по обидва боки від має лишитися щонайменше по два ліхтарі.

Коли відповідь існує. Розглянемо окремий цикл довжини : колір може зустрічатися в ньому щонайбільше разів (інакше два однакові неминуче стануть поруч). Наші цикли мають довжини x+1 і y+1, а x + y + 1 = n, тож найбільша кількість однакових ліхтарів, яку взагалі можна вмістити, дорівнює

\max_{x,\,y \ge 2} \Bigl( \bigl\lfloor \tfrac{x+1}{2} \bigr\rfloor + \bigl\lfloor \tfrac{y+1}{2} \bigr\rfloor \Bigr) = \Bigl\lceil \tfrac{n}{2} \Bigr\rceil .

Максимум досягається, коли обидві довжини парні (для непарного : 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 і виводимо

\underbrace{p\ q\ p}_{\text{верх}}, \qquad \underbrace{q}_{\text{перехрестя}}, \qquad \underbrace{p\ q\ p\ q\ \ldots\ p}_{\text{низ}} .

Обидві петлі парної довжини, кольори в них чергуються, а перехрестя отримує рідший колір — рівно так і виходить різниця в одиницю.

Побудова для 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), якщо розкладати кольори по кошиках).