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

A. Громадянська війна

У даній задачі достатньо просимулювати процес з умови, використовуючи цикл while.

B. Зеник-садівник

Неважко переконатися, що наступний паттерн задовольняє умову задачі:

xoxoxo...

xoxoxo...

oxoxox...

oxoxox...

xoxoxo...

xoxoxo...

.........

С. Зеник-шахрай

Покажемо, що Зенику оптимально видалити або якусь кількість сторінок з початку, або з кінця щоденника. Припустимо, що Зеник вирвав якісь сторінки $L, L + 1, …, R$ з середини щоденника, але залишив і першу, і останню сторінки (тобто $1 < L \le R < n$). Тоді розглянемо середнє арифметичне оцінок на сторінках $[1, L - 1]$ (нехай це буде якесь число $А$), і середнє арифметичне оцінок на сторінках $[R + 1, n]$ — $B$. Якщо $B \le A$, то Зеник міг би вирвати всі сторінки від $L$ до $n$, при цьому не погіршивши загальне середнє, а якщо $A \le B$, то він би міг вирвати всі сторінки від 1 до $R$, також не погіршивши загальне середнє.

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

D. Могилізація

Розв’яжемо дану задачу для двох точок $(x_1, y_1)$ і $(x_2, y_2)$. Якщо $x_1 + y_1 \mod 3 \neq x_2 + y_2 \mod 3$, то відповіді не існує, оскільки ходи не змінюють остачу від ділення на 3 для суми координат. Неважко переконатись, що існує єдина точка $(x, y)$, у яку можна пересунути точки, використовуючи мінімальну кількість ходів.

Уміючи розв’язувати задачу для 2 точок, ми можемо зводити задачу з розміру $n$ до розміру $n - 1$ поки $n \ge 2$.

E. Хаймарс-2

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

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

F. Зеник-програміст

Для початку посортуємо роботи за прибутком. Обчислимо масив $q$ з імовірностями потрапити на роботу кращу за $i$ за один місяць.

$q_n = 0, q_{n-1} = p_n, q_{n-2} = q_{n-1} + (1 - p_n) (p_{n-1}), q_{n-3}=...$

Далі будемо рахувати вклад роботи $i$ у відповідь. Легко бачити, що перша робота приносить значення $a_1 \cdot \sum_{j=1}^{m}(1 - q_1)^j$ до відповіді. Для 2 роботи вклад можна порахувати за допомогою принципу включення-виключення: $a_2 \cdot \sum_{j=1}^{m}((1 - q_2)^j - (1 - q_1)^j)$. У цій формулі $(1 - q_2)^j$ означає що Зенику не вдалось потрапити на роботу кращу за 2, $(1 - q_1)^i$ потрібно відкинути, щоб виключити імовірність залишитись у першій компанії. Аналогічно значення можна порахувати для роботи $i$.

Суму $\sum_{j=1}^{m}(1 - q)^j$ порахуємо використовуючи формулу суми геометричної прогресії.

G. Зеник-бізнесмен

Припустимо Зеник найняв вже $k$ людей. Розглянемо початкову множину їх зарплат $A$. Зрозуміло, що не має сенсу подвоювати зарплату працівнику з найбільшою початковою зарплатою. Для кожного іншого працівника, будемо подвоювати його зарплату допоки вона не стане більшою за $max(A) / 2$.

Тепер посортуємо всіх працівників за новими зарплатами — $a_1 \le a_2 \le a_3 ... \le a_k < 2a_1$. Зрозуміло, що з цього моменту часу все, що може зробити Зеник це подвоїти зарплати якійсь кількості працівників з найменшими зарплатами. Якщо Зеник залишить все як є, то нерівність буде $a_k - a_1$. Якщо ж він подвоїть зарплати першим $1 \le i < k$ працівникам, то нерівність буде $2a_i - a_{i+1}$. Тому підтримуватимемо множину $S$ таких значень.

Припустимо тепер Зеник захоче найняти ще одного працівника з початковою зарплатою $x$. Аналогічно подвоюватимемо цю зарплату доки вона не перевищить $max(A) / 2$. Тепер є два випадки:

1. $x \le max(A)$. Тоді якщо $a_i \le x \le a_{i+1}$, то потрібно видалити з множини $S$ число $2a_i - a_{i+1}$ та вставити два нові відповідні числа (якщо $x < a_1$, то просто вставити одне нове число).

2. $x > max(A)$. Тоді додамо $x$ в множину $А$ та почергово будемо подвоювати зарплату найменш оплачуваному працівнику, аби знову досягти вищеописаного інваріанта $min(A) * 2 > max(A)$. Підтримуватимемо при цьому актуальні значення множини $S$.

Можна помітити, що впродовж всього часу жоден працівник не отримає подвоєнь зарплати більше аніж $\log (max(A))$ разів. Тому сумарна кількість подвоєнь продовж всього процесу — $O(n \log (max(A))$, а кожну таку операцію можна виконувати за час $O(\log n)$ використовуючи, наприклад, set або map. Тому сумарна складність становитиме $O(n \log n \log(max(A))$.