Choose Colors#245

Choose Colors (Editorial)

Кожне коло з $a_{i} + 1$ a_i + 1 кольорів після викреслення одного кольору перетворюється на один відрізок незакреслених кольорів довжини $a_{i}$ a_i. Далі коло вже не має значення — уся задача живе на мультимножині довжин відрізків.

Що робить один крок? Береться найдовший відрізок довжини $L$ , з нього викреслюється середина, і він розпадається на два відрізки довжин

⌊ \frac{L}{2} ⌋ та ⌊ \frac{L - 1}{2} ⌋

\left\lfloor \frac{L}{2} \right\rfloor \quad \text{та} \quad \left\lfloor \frac{L-1}{2} \right\rfloor

(їхня сума дорівнює $L - 1$ L - 1, бо одна клітинка зникає). Порожні відрізки просто зникають.

Моделювати $m \leq 1 0^{18}$ m \le 10^{18} кроків по одному неможливо. Але тут працює важливе спостереження: алгоритм завжди бере найдовший відрізок, тому всі відрізки однакової максимальної довжини будуть оброблені підряд, перш ніж черга дійде до коротших. Отже, кроки природно групуються в «раунди»: за один раунд ми обробляємо всі $c$ відрізків поточної максимальної довжини $L$ одразу.

Крім того, довжини щоразу приблизно вдвічі зменшуються, тому різних довжин у мультимножині завжди небагато — порядку $lo g (max a_{i})$ \log(\max a_i), тобто кілька десятків. Тому зберігати мультимножину зручно як відсортований список пар «довжина — кількість».

Алгоритм:

беремо найбільшу довжину $L$ з кількістю $c$ ;
якщо кроків, що залишилось зробити, менше за $c$ , то саме $L$ і є відповіддю — це максимальна довжина відрізка перед потрібним вибором;
інакше віднімаємо $c$ від лічильника кроків, викидаємо $L$ зі списку і додаємо по $c$ відрізків довжин $⌊ L /2 ⌋$ та $⌊(L - 1) /2 ⌋$ \lfloor (L-1)/2 \rfloor (нульові пропускаємо).

Зверніть увагу, що нас цікавить стан перед вибором $(m + n)$ (m+n)-го кольору, тобто після $m - 1$ m - 1 додаткових кроків.

Технічна порада: кількості відрізків подвоюються з кожним раундом, тому в мовах із фіксованою розрядністю вони можуть переповнити 64-бітний тип. Оскільки нас цікавить лише порівняння з числом кроків (не більшим за $1 0^{18}$ 10^{18}), достатньо обмежувати лічильники зверху якоюсь константою на кшталт $2 \cdot 1 0^{18}$ 2 \cdot 10^{18}.