Пінгвіни#495

Пінгвіни (Розбір)

Автор: Тимур Дегтярі

Роздробник: Тимур Дегтярі

Розбір підготовано: Тимур Дегтярі, Костянтин Денисов

Ми стверджуємо, що відповідь . Дійсно, розглянемо наступний жадібний підхід:

  • проходимо через сім'ї, призначаємо поточну сім'ю команді найменшого розміру. Розглянемо, як змінюються найменший і найбільший розміри команди:

  • нехай буде мінімумом, а — максимумом. Припустимо, що y-x \le 3. Тоді після призначення поточної сім'ї найменшій команді новий мінімум становить принаймні , а новий максимум — \max(x+3, y) \le x+3. Отже, ця властивість зберігається протягом усього процесу призначення.

Отже, відповідь завжди одна з 0, 1, 2, 3.

Нехай — це кількість сімей з пінгвінами, — з пінгвінами, а — з пінгвіном. Нехай S = 3 \cdot x + 2 \cdot y + z.

Ствердження: якщо (x\ \%\ k) > 0 і (x\ \%\ k) + y + z < k, відповідь дорівнює .

Нехай t = \lfloor \frac{x}{3} \rfloor. Спочатку зауважимо, що в оптимальному призначенні принаймні одна команда матиме пінгвінів. Оскільки (x\ \%\ k) + y + z < k, за принципом Діріхле принаймні одна команда міститиме лише сім'ї з пінгвінами. Якщо ця команда має розмір 3t+3, тоді, щоб відповідь не була , всі інші команди повинні мати розміри \ge 3t+1, тому кожна з них повинна містити або принаймні одну сім'ю розміру , або , або принаймні t+1 сімей розміру , отже, (x\ \%\ k) + y + z \ge k-1. Водночас команда, яку ми розглядаємо, також має t+1 сімей з , отже, (x\ \%\ k) + y + z \ge k, що є суперечністю.

Якщо ця команда має розмір не більше 3t-3, тоді за принципом Діріхле найбільша команда має розмір принаймні \frac{S}{k} > 3t, що дає відповідь , суперечність. Отже, завжди є принаймні одна команда з розміром .

Більше того, це єдиний випадок, коли відповідь дорівнює . Припустимо, що (x\ \%\ k) + y + z \geq k. Спочатку рівномірно розподіліть сім'ї з між командами, так що команд мають 3t+3 пінгвінів, а решта команди мають пінгвінів. Тепер розподіліть достатньо сімей з і пінгвінами, щоб усі команди мали розміри між 3t+1 і 3t+3. Оскільки залишилися лише сім'ї з і , а різниця в розмірах становить не більше , ми можемо зберігати її не більше , жадібно додаючи нову сім'ю до найменшої команди, отже, оптимальна відповідь не перевищує .

Крім того, якщо (x\ \%\ k) + y + z < k, але (x\ \%\ k) = 0, очевидно, що відповідь дорівнює , якщо y > 0; , якщо y=0, z>0, і , якщо y=z=0.

Отже, тепер нам потрібно лише розрізнити, чи відповідь дорівнює або .

Цілі для відповідей 0 і 1.

Перевірка ans=0. Якщо S\bmod k\ne 0, тоді ans=0 неможливо. В іншому випадку всі команд повинні мати однаковий розмір T=S/k.

Перевірка ans=1. Нехай L=\lfloor S/k\rfloor, U=L+1, а x=S-kL. Тоді точно команд повинні мати розмір , а решта k-x команд повинні мати розмір .

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

Жадібна процедура перевірки TryBuild.

Нам дано мультимножину цільових розмірів команд (або всі , або k-x копій і копій ). Ми також підтримуємо залишкові кількості (c_1,c_2,c_3) і намагаємося побудувати кожну команду незалежно.

Перший прохід (жадібний на основі шаблону). Для кожного цільового розміру (обробляємо цілі в невисхідному порядку) ми намагаємося заповнити одну команду з загальною сумою точно за наступними пріоритетами:

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

  2. Поки це можливо, розміщуйте пари (віднімемо від ), поки t\ge 6.

  3. Потім, поки це можливо, розміщуйте пари (віднімемо ), але лише після завершення етапу .

  4. Потім розмістіть якомога більше сімей з (віднімемо щоразу).

  5. Нарешті, розмістіть пари (віднімемо ).

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

Другий прохід (найбільша сім'я в найменшу команду). Якщо перший прохід зазнає невдачі, ми починаємо з початкових кількостей і запускаємо ще один жадібний:

  • Зберігайте команд з їхніми поточними сумами (спочатку всі ) у структурі, яка може повертати команду з найменшою сумою.

  • Постійно беріть найбільшу залишкову сім'ю (надаючи перевагу розміру , потім , потім ) і додавайте її до найменшої команди.

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

Складність.

Підрахунок c_1,c_2,c_3 — це . Другий жадібний прохід можна реалізувати за допомогою пріоритетної черги над командами і виконується за O(n\log k). Загальна складність на тестовий випадок становить O(n\log k).