Короткий розбір The Algo Battles 2024 - Етап 1 | Статті

Можна або знайти суму і мінімум, або посортувати усі вартості та додати всі крім найменшої.

Поставимо значення 1, 2, $\dots$ , $\left \lceil{\frac{n}{2}}\right \rceil$ в такому порядку на непарні позиції, та значення $\left \lceil{\frac{n}{2}}\right \rceil + 1$ , $\dots$ , $n$ на парні. Наприклад, для $n=7$ вийде [1, 5, 2, 6, 3, 7, 4].

У такій побудові $a_{i+2}=a_i+1$ , а отже $a_{i+1}+a_{i+2}=a_i+a_{i+1}+1$ . Тобто усі значення $a_i+a_{i+1}$ будуть рівні $x, x+1, \dots, x+n-2$ , де $x=a_1+a_2$ .

Всі такі значення дають різні остачі при діленні на $n$ .

С. Паліндромно менший рядок

Якщо в рядку $s$ є 1 чи 2 різні символи, то не вийде використати менше, а отже можна взяти $t=s$ .

Далі якщо взяти $t$ =abcabcab..., то в $t$ немає підрядків паліндромів крім підрядків з 1 символа. Отже, $t$ буде палідромно меншим за $s$ .

Можливо показати, що неможливо, щоб в $t$ було менше ніж 3 різних символів, якщо розглянути підрядок $s$ вигляду ab...bc.

D. Найдовша прогулянка

Існує не більше 24 різних маршрутів. Це так, бо більшість поворотів буде відбуватись в куті поля (якщо видаляти вже відвідані клітинки), а отже буде тільки 1 варіант куди іти далі.

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

E. Перестановка з двох масивів

Розглянемо кожен біт окремо. Подивимось скільки в результаті повинно бути чисел, в яких цей біт 1 і скільки таких, в яких 0. Позначимо це $c_0$ та $c_1$ . Якщо $c_0 \ne c_1$ , то існує не більше одного варіанту, яким цей біт може бути в $x$ та $y$ . Це так тому, що $n$ та $m$ непарні. Розглянемо випадок, коли $c_0=c_1$ . Таке можливо лише якщо $n+m$ ділиться на $2^{bit+1}$ , а також якщо всі елементи перестановки проксорити з $2^{bit}$ , то це теж буде перестановкою. Тобто в цьому випадку можливими є 2 варіанти, якими значеннями можуть бути біти в $x$ та $y$ , обидва нам або одночасно підходять, або не підходять. Спробуємо будь-який з них, перевіримо чи в результаті вийшла перестановка. Якщо так, то відповідь рівна $2^k$ , де $k$ — найбільший степінь 2, що ділить $n+m$ .

Іншим розв’язком буде подивитись на xor усіх чисел. З цього можливо знайти $x\ xor\ y$ . Замінимо всі значення другого масиву $b_i := b_i\ xor \ (x\ xor\ y)$ . Далі обидва масиви потрібно ксорити з $x$ , подивимось чи немає однакових значень. Можна перебрати, яке значення буде в результаті 0 та префіксним деревом перевірити, чи всі решта чисел виходять менші $n+m$ . Або також можна для кожного значення згенерувати проміжки $x$ , коли значення будуть менші $n+m$ .

F. Каркас веж

Розглянемо 3 вежі $x_1 < x_2 < x_3$ та $y_2 \ge min(y_1, y_3)$ . Використовувати кабель між 1 і 3 вежею не вигідно: або ми не можемо його провести або вигідніше його замінити на менші кабелі, бо $dist(1, 3) > dist(1, 2)$ та $dist(1, 3) > dist(2, 3)$ .

Тепер нас цікавлять тільки такі пари веж, що всі вежі між ними менші за обидві крайні. Зрозуміло, що такий кабель не буде перетинатись з іншими вежами. А також таких пар веж є $O(n)$ , згенерувати їх можна, якщо розглядати вежі зліва направо та підтримувати спадний стек.

Тож згенеруємо всі такі пари та знайдемо найменший каркас алгоритмом Крускала.

G. Побітова імплікація

Розглянемо останню операцію, нехай вона $x \to y$ . Нам потрібно, щоб для конкретного біта, в $x$ цей біт був 1, а в $y$ 0.

Припустимо, що ми отримали $y$ використовуючи операцію $y=y_1 \to y_2$ . Тоді $x \to y = x \to (y_1 \to y_2) = x \to (!y_1\ |\ y_2)$ . Якщо ж з іншого боку залишити $y_2$ для останньої операції і зробити операцію $y_1 \to x$ , то вийде $(!y_1\ |\ x) \to y_2$ . Таким чином ми отримаємо не гірше значення і зліва і справа — зліва буде не менше 1, а справа не менше 0. З цього можна зробити висновок, що $y$ має бути одним з оригінальних чисел набору. Переберемо його і залишимо тільки ті біти, де 0.

Ми можемо отримати $x =\ !a_1\ |\ !a_2\ |\ \dots\ |\ !a_{i-1}\ |\ !a_{i+1}\ |\ \dots\ |\ !a_n\ |\ a_i$ , тобто усі значення крім одного з запереченням. Щоб в такому значенні був біт 0 потрібно, щоб у всіх крім одного значеннях, цей біт був 1, а в одному 0.

Назвемо біт унікальним, якщо він рівний 0 в рівно одному значенню. Назвемо значення унікальним, якщо воно містить хоча б один унікальний біт. Якщо існує не унікальне значення, то можна отримати $x=2^k-1$ , якщо його обрати як значення без заперечення. Якщо $n>k+1$ , то точно існує неунікальне значення, а отже $x=2^k-1$ .

Інакше все одно можна розглядати лише значення $x =\ !a_1\ |\ !a_2\ |\ \dots\ |\ !a_{i-1}\ |\ !a_{i+1}\ |\ \dots\ |\ !a_n\ |\ a_i$ . Це так тому, що які б операції ми не робили, унікальні біти одного з початкових значень залишаться 0. А розглядаючи тільки такий вигляд в нас вийдуть всі інші біти 1.

Тому для кожного запиту, якщо $r - l + 1 > k+1$ , то відповідь рівна мінімальній кількості одиничних бітів на проміжку. Якщо $r-l+1 \le k+1$ , то можна перебрати, яке значення $y$ та яке значення беремо в $x$ без заперечення. Тобто відповідь на запит можна знайти за $O(k^2)$ .