Stone Pairs#259

Stone Pairs (Editorial)

Автор задачі:	Роман Білий
Задачу підготував:	Роман Білий
Розбір написав:	Роман Білий

Назвемо однією операцією сумарний хід Аліси та Боба. Якщо вони вибирають всі 4 купки різні, то вони фактично вибирають 4 числа $(x, x, y, y)$ (x, x, y, y) та змінюють їх на $(x - 1, x - 1, y - 1, y - 1)$ (x-1,x-1,y-1,y-1). А якщо купки збігаються, то нехай Аліса вибрала $(x, y)$ , то щоб Боб міг взяти одну з купок, яку взяла Аліса, потрібно, щоб було $y = x - 1$ y=x-1. В результаті вийде, що з $(x, x, x - 1)$ (x, x, x-1) утворились купки $(x - 2, x - 2, x - 1)$ (x-2, x-2, x-1).

Тобто є 2 можливі операції:

$(x, x, y, y) \to (x, x, y, y)$ (x, x, y, y)\ \to\ (x, x, y, y)
$(x, x, x - 1) \to (x - 2, x - 2, x - 1)$ (x, x, x-1)\ \to\ (x-2, x-2, x-1)

Тепер ми хочемо зробити якнайбільше операцій цих 2 типів і якщо в кінці залишаться хоча б 2 ненульові купки, то Аліса зможе зробити ще 1 свій хід.

Блок 1

У блоці 1 можна зробити повний перебір всіх можливих операцій. Щоб зменшити кількість станів, будемо тримати масив розмірів купок посортованим.

Блок 2

Розіб'ємо всі значення на пари. Нехай ми робимо операції тільки першого типу. За одну операцію можна вибрати 2 пари та зменшити їх на 1. Така задача розв'язується наступним чином. Нехай $b_{i}$ b_i — значення в парах, $k$ — кількість пар(в даному блоці $k = n /2)$ k=n/2). Посортуємо їх по спаданню, тобто $b_{1}$ b_1 — найбільше значення. Якщо $b_{1} \leq \sum_{i = 2}^{k} b_{i}$ b_1 \le \sum_{i=2}^k b_i, то ми зможемо всі пари звести до 0, крім можливо одної, яка буде рівна 1, залежно від парності. Інакше ми можемо звести всі пари до 0, а найбільшу до $b_{1} - \sum_{i = 2}^{k} b_{i}$ b_1-\sum_{i=2}^k b_i.

З цього також слідує, що використовувати операцію 2 типу не вигідно. Якщо є пари $x$ та $x - 1$ x-1 і жодна з них не найбільша, то ми тільки зменшимо $\sum_{i = 2}^{k} b_{i}$ \sum_{i=2}^k b_i. Якщо пара $x$ — найбільша, то і операціями першого типу ми отримаємо найкращий результат.

Блоки 3-5

З опису операцій видно, що операції виконуються з парами. Тому якщо є непарна кількість значень $x$ , то одне з них таким ж і залишиться. Назвемо такі купки стоячими. Після цього знову розіб'ємо всі інші купки на пари. Як і в розв'язку до попереднього блоку поганий є випадок, коли $b_{1} > \sum_{i = 2}^{k} b_{i}$ b_1 > \sum_{i=2}^k b_i. Тепер спробуємо використати стоячі купки і 2 операцію. 2 операцію вигідно використовувати тільки для найбільшої купки. Тобто якщо зараз найбільша купка рівна $x$ і є стояче значення $x - 1$ x-1, то перестрибнемо найбільшою купкою через це стояче значення і найбільша купка тепер буде рівна $x - 2$ x-2. Тобто знайдемо, яке кінцеве найменше значення зможе мати найбільша купка. Спочатку вона буде рівна $r = b_{1} - \sum_{i = 2}^{k} b_{i}$ r=b_1-\sum_{i=2}^k b_i. Далі будемо пробувати перестрибувати через стоячі купки. Якщо є стояча купка в межах $[r - 1, b_{1} - 1]$ [r-1, b_1-1], то через неї можна перестрибнути і зменшити $r$ на 2. Але не можна перестрибнути через стоячі купки з сусідними значеннями, тобто через $y$ та $y - 1$ y-1. У блоці 3 таких сусідних значень бути не могло.

Тобто розв'язок такий:

Розіб'ємо всі значення на пари.
Якщо $b_{1} \leq \sum_{i = 2}^{k} b_{i}$ b_1 \le \sum_{i=2}^k b_i, то у всіх парах залишиться максимум одна пара зі значеннями 1 залежно від парності.
Інакше знайдемо значення найбільшої купки, яке ми можемо отримати використовуючи тільки операції 1 типу $r = b_{1} - \sum_{i = 2}^{k} b_{i}$ r=b_1-\sum_{i=2}^k b_i. Посортуємо всі стоячі купки до спаданню і спробуємо перестрибувати через них. Але перестрибувати через дві стоячі купки з сусідніми значеннями не можна.
Знайдемо, чи залишились 2 непусті купки і в такому разі Аліса може зробити ще 1 хід.

Складність розв'язку $O (n lo g (n))$ O(n \log(n)).