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

A. Кредитнi картки

В задачі потрібно просто зробити те, що сказано в умові. Для спрощення написання коду, можна не будувати нову стрічку, а одразу рахувати суму.

Код розв’язку.

Цікавий факт: крім банківських карток алгоритм Луна використовується для IMEI та номерів соціального страхування в Канаді.

B. Розклад на множники

Будемо перебирати $p_i$ та ділити $n$ на $p_i$, поки $n$ ділиться на $p_i$ без остачі. Якщо після цих операцій ми отримали одиницю — відповідь YES, інакше NO.

Код розв’язку.

Цікавий факт: на квітень 2023, найбільше відоме людству просте число $2^{82589933}-1$. Це число має $24862048$ цифр.

С. Найближчi точки

Задачу можна розв’язувати незалежно по $x$ і $y$. Для однієї із координат відповіддю завжди буде одна із сусідніх пар в посортованому масиві. Достатньо вибрати із двох відповідей меншу. Під час сортування треба бути обережним, щоб також мінімізувати $i+j$. Для цього слід сортувати не лише по координаті, а й по номеру.

Код розв’язку.

Цікавий факт: Точка-У здатна гатити орків на відстані до 120км.

D. Помаранчева революцiя

Нескладно помітити, що якщо $b=c$, ми можемо досягти Помаранчевої Революції зробивши $b$ червоно-голубих зустрічей.

Подивимося уважно, що стається із $(b-c)$ після зустрічі оранжевого і голубого:

$$\begin{gathered} a' = a - 1 \\ b' = b - 1 \\ c' = c + 1 + 1 + k \\ b' - c' = (b - c) - \textbf{(k+3)} \end{gathered}$$

Аналогічно після зустрічі оранжевого і червоного

$$\begin{gathered} a' = a - 1 \\ b' = b + 1 + 1 + k \\ c' = c - 1 \\ b' - c' = (b - c) + \textbf{(k+3)} \end{gathered}$$

Бачимо, що різниця не міняє остачі від ділення на $(k+3)$. Отже якщо $(b-c)$ не ділиться на $(k+3)$ націло, то отримати $b=c$ неможливо і відповідь NO. Інакше відповідь YES. Для знаходження порядку зустрічей застосуємо жадібний підхід.

Код розв’язку.

Цікавий факт: Вважають, що давні єгиптяни одними з перших бджолярів в світі.

E. Рамки Малевича

Розгленемо будь-яку сторону квадрата. Припустимо ми зафіксували кутики. Можливо показати, що якщо обидва кутики є випуклими, то сторона буде валідною тоді і тільки тоді, якщо кількість частинок 5-го типу є на один більшою ніж 6-го. Аналогічно, якщо обидва кутики є впуклими, то кількість частинок 6-го типу має бути на один більшою за кількість частинок 5-го. Якщо ж кутики різного типу, то кількість частинок 5-го і 6-го типів повинна бути однаковою. Кількість частинок 7-го типу може бути будь-якою.

Переберемо парність $n$ і кутики. Для кожної сторони виставимо обов’язкові частинки - можливо одну з 5-го або 6-го типу і можливо одну 7-го, щоб була потрібна парність. Після цього можна добирати будь-яку кількість пар - 5 і 6 або дві 7.

Тож ми можемо перебрати усі можливо рамки розміру 3х3 та 4х4 і максимізувати кількість можливих пар. Тоді щоб збільшити $n$ на 2 потрібно використати 4 пари. Перебирати можна кутики з виставленням необхідних частинок. Або можна перебрати усі $2^8$ та $2^{12}$ варіантів з’єднань.

Код розв’язку з перебором кутиків

Код розв’язку з перебором варіантів

Цікавий факт: Вважають, що аматорським малюванням Казимир Малевич почав займатися в Конотопі.

F. Пляцок

Програшні позиції — многокутники, для яких відстань від лівого краю до правого рівна відстані від нижнього до верхнього $max(x_i) - min(x_i) = max(y_i) - min(y_i)$ (назвемо такі многокутники обрізаними квадратами), і з них за одну операцію не можна відрізати многокутник з такими ж характеристиками. Можна довести, що з обрізаного прямокутника завжди можна за одну операцію вирізати обрізаний квадрат, з якого в свою чергу за одну операцію не можна вирізати обрізаний квадрат, тільки прямокутник: $max(x_i) - min(x_i) \ne max(y_i) - min(y_i)$. Для цього підійде обрізаний квадрат найменшого розміру.

Імплементація: йдемо з лівого краю многокутника до правого і підтримуємо найвищу і найнижчу точку, таким чином ми знаємо: $min(x_i)$ — лівий край, $max(y_i)$ — координата $y$ найвищої розглянутої точки, $min(y_i)$ — координата $y$ найнижчої розглянутої точки, $max(x_i)$ — поточна $x$ координата. Якщо в якийсь момент до досягнення правого краю рівність буде виконуватись, то виграє перший гравець. Аналогічний прохід треба зробити зліва направо, зверху вниз і знизу вверх. Якщо рівність ніколи не виконається — виграє другий гравець. Складність $O(dx + dy + n)$.

Код розв’язку.

Цікавий факт: найбільший спечений пляцок важив 10540 кг.

G. Налийте якомога швидше

Проходимо по масиву часткових різниць зліва направо і підтримуємо кількість відкритих проміжків висоти 1 (ціна створення 1) та відкриті проміжки висоти $x$ (ціна створення 1, але їх можна розбити на $x$ одиничних проміжків за певну ціну). Проміжків висоти 1 в нас завжди буде менше, ніж $х$; якщо більше, то поміняємо їх на один проміжок $х$ з ціною розбиття 0. Маємо два випадки:

• Часткова різниця $a$ додатня. Поки $a \ge x$ додаємо проміжок $x$ з ціною $x-1$ та 1 до відповіді. Залишилось $a < x$, треба або відкрити $a$ проміжків висоти 1 або відкрити 1 проміжок висоти $x$ і закрити $x-a$ проміжків висоти 1. Якщо кількість відкритих проміжків висоти 1 не менше $x-a$: тоді закриваємо $x-a$ одиничних і додаємо один проміжок висоти $x$ з ціною $a-1$, +1 до відповіді. Інакше, збільшуємо кількість відкритих одиничних відрізків на $a$ і якщо вигідніше розбити найдешевший (нехай його ціна $p$) $x$ проміжок для об’єднання $p + 1 < x$, то розбиваємо його і додаємо до відповіді $p+1$ і формуємо новий $x$ проміжок з ціною $a-1$, інакше просто додаємо до відповіді $a$.

• Часткова різниця $-a$ від’ємна. Аналогічно поки $a \ge x$ закриваємо найдорожчий проміжок висоти $x$. Тепер ми можемо або закрити $a$ проміжків висоти 1 і нічого не платити, або закрити один $x$ і відкрити $x-a$ 1 і заплатити $x-a$. Якщо в нас є $a$ проміжків висоти 1, то закриваємо їх і міняємо проміжок висоти $x$ на інший з ціною $x-a$ якщо це вигідно (вона менша). Якщо немає, тоді можливо вигідно поміняти найдешевший (нехай його ціна $p$) $x$ на проміжки висоти 1. Тоді в першому випадку ми платимо $p$, в другому $x-a$. Тобто якщо $p < x - a$, то заплатимо $p$, закриємо цей проміжок висоти $x$ і можемо змінити найдорожчий відрізок $x$ на інший з ціною $x-a$; інакше заплатимо $x-a$ і видалимо найдорожчий відрізок $x$ (треба видалити відрізок ціною $x-a$ і можна замінити найдорожчий відрізок $x$ на інший з ціною $x-a$ => просто видалимо найдорожчий відрізок $x$).

Складність $O(n \cdot log(n))$.

Код розв’язку.

Цікавий факт: Бар Шона в Ірландії працює безперервно ще з середньовіччя.