Розбір

A. «Камiнь-ножицi-папiр»

Порахуємо, скільки разів Марічка може виграти каменем. Ця кількість не може бути більша за кількість ігор, у яких Марічка поставила камінь, і не може бути більша за кількість ігор, у яких Зеник поставив ножиці, тобто $min(r_M, s_Z)$. Аналогічно, кількість ігор, у яких Марічка може перемогти ножицями й папером рівна $min(s_M, p_Z)$ i $min(p_M, r_Z)$, відповідно. Відповідь до задачі буде рівна сумі цих трьох доданків.

Код розв’язку С++

B. Пошук паліндрома

Нехай кількість одиниць рівна $a$, а кількість нулів рівна $b$. Якщо $a \le b$ тоді $2 \cdot a \le a + b = n$. Тому одиниць є не більше ніж половина, і якщо ми видалимо їх усіх, то отримаємо рядок з нулів, який є паліндромом. Аналогічно, коли $b \le a$, ми можемо видалити всі нулі й отримати рядок з одиниць, який також є паліндромом.

Код розв’язку С++

C. Найкраща назва

Можна зауважити, що оптимальний рядок — це конкатенація рядків виду bohdan, danylo, maksym та bohdanylo. Без обмеження загальності, уважатимемо, що $d \le b$, а отже немає сенсу використовувати рядок danylo в нашій назві (якщо він не є частиною рядка bohdanylo).

Розглянемо два варіанти:

Не використовувати рядок maksym у назві. Припустимо, що в оптимальній назві рядок bohdan зустрічається принаймні 9 разів, а bohdanylo — принаймні 6 разів. Тоді при заміні дев’яти рядків bohdan на шість рядків bohdanylo (або навпаки) прибуток не зменшиться, а отже існує оптимальна назва, де кількість рядків bohdan менша ніж 9, або кількість рядків bohdanylo менша ніж 6. Тому переберемо кількість рядків bohdan від 0 до 8, а рeшту вільного місця виділимо під рядок bohdanylo (та навпаки). У такий спосіб ми отримаємо оптимальну назву для команди.
Використаємо рядок maksym принаймні один раз. Тоді легко бачити, що рядки maksym ітимуть поряд, і для $1 \le k$ рядків maksym потрібно рівно $5k + 1$ символів. Аналогічно до попереднього пункту, можна показати, що існує оптимальна назва, у якій або кількість рядків maksym, або bohdan, або bohdanylo не перевищує, наприклад, 20 (існують і строгіші оцінки). Тому перебравши кількість рядків одного із цих типів, зведемо отриману задачу до попереднього пункту (див. код для кращого розуміння).

Складність розв’язку: $O(1)$ часу та пам’яті.

Код розв’язку С++

D. Розбиття на прямокутники

Розв’язок зі складністю $O(nmk)$. Переберемо всі можливі $a$ і $b$ та перевіримо, чи точки, що з’єднані між собою, належать різним прямокутникам.

Розв’язок зі складністю $O(n(m^2+k))$. Переберемо $a$. Якщо для деяких з’єднаних точок $(x_1, y_1), (x_2, y_2)$ виконується $\left \lfloor{\frac{x_1}{a}}\right \rfloor \ne \left \lfloor{\frac{x_2}{a}}\right \rfloor$, то ці точки будуть у різних прямокутниках. Тепер розглядаємо лише ті пари точок, для яких ця умова не виконується. Треба задовольнити умову $\left \lfloor{\frac{y_1}{b}}\right \rfloor \ne \left \lfloor{\frac{y_2}{b}}\right \rfloor$.

Тепер маємо одновимірну задачу. Для її розв’язання заведемо масив $d$. Значення $d[i]$ означає найменшу $y$-координату, не меншу за $i$, серед усіх точок, що з’єднані з якоюсь точкою з $y$-координатою рівною $i$. Іншими словами, це координата найближчої зверху точки, з’єднаної з точкою з $y$-координатою рівною $i$. Після обчислення такого масиву можемо перебрати $b$ та перевірити, чи виконується умова $\left \lfloor{\frac{i}{b}}\right \rfloor \ne \left \lfloor{\frac{d[i]}{b}}\right \rfloor$ для всіх $i$.

Код розв’язку С++

A. Соціальна дистанція

Потрібно перевірити для всіх $i$ умову $x_{i+1}-x_i \ge 2$.

Код розв’язку С++

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

B. Розповсюдження вірусу

Один з варіантів, що дає максимальну кількість будинків з хворими — це коли початкові $k$ будинків з хворими знаходяться поруч на одній діагоналі. Тоді відповідь буде рівна $k^2$, але кількість будинків з хворими не може бути більшою за кількість будинків у місті. Отже, відповідь — min($k^2$, $n^2$).

Код розв’язку С++

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

C. Захисні маски

Зеник може в кожному магазині купувати одноразову маску. У цьому разі він заплатить $\sum_{i=1}^n a_i$. Цей дивний запис означає суму $a_i$ за всіма $i$ від 1 до $n$.

Якщо ж він вирішить придбати багаторазову маску в $j$-ому магазині, то йому доведеться купити одноразові маски в усіх магазинах перед $j$-им. Тоді він витратить $b_j + \sum_{i=1}^{j-1} a_i$. Можна перебрати $j$ — індекс магазину, де найвигідніше придбати багаторазову маску. Для цього будемо йти індексом $j$ від 1 до $n$ і підтримувати значення суми $a_i$ на префіксі.

Відповіддю буде найменший серед усіх цих варіантів.

Код розв’язку С++

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

D. Небезпечні друзі

Розглянемо граф, вершинами якого будуть люди, причому деякі пари з них будуть з’єднані ребрами, що означатиме дружбу між відповідними людьми.

Запустимо пошук у глибину (або в ширину) з кожної вершини, відповідна людина якої була хворою у початковий момент часу, та помічатимемо відвідані вершини. Важливо не відвідувати вершину 1, а також раніше оброблені вершини. Наприкінці множина помічених сусідів вершини 1 буде відповідати множині друзів, з якими варто обірвати всякі контакти на час пандемії (адже ці друзі можуть стати зараженими).

Складність такого розв’язку — лінійна відносно розміру вхідних даних.

Код розв’язку С++

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

A. А ти вже помив руки?

У цій задачу потрібно лише зчитати числа $a, b, k$ та вивести $a+b \cdot k$.

Код розв’язку С++

B. Усе погано

Якщо в кожному рядку буде хоча б один заражений квартал, або в кожному стовпці буде хоча б один заражений квартал, тоді відповідь — YES, оскільки ці віруси можуть кожен вибрати свій рядок або стовпець і в результаті заразити все поле. У протилежному разі — відповідь NO, оскільки буде хоча б одна клітинка, у якої в рядку та стовпці немає жодної зараженої клітинки, і тому вона ніколи не стане зараженою.

Код розв’язку С++

C. Знезаражувач реп’яховіруса

Із заданої множини чисел розміром $n$ необхідно вибрати $k$ чисел так, щоб їх сума була непарною.

Поділимо усі числа на дві множини: парні і непарні. Для того щоб сума вибраних чисел була непарною, необхідно вибрати непарну кількість непарних чисел. Далі задачу можна розв’язувати багатьма способами. Один з можливих розв’язків наступний: візьмемо одне непарне число. Тоді, поки ще треба брати числа, і є хоча б два непарних числа, будемо брати по два непарних числа. Якщо після цього необхідно добрати ще чисел, добираємо парні. Якщо ми таким процесом вибрали рівно $k$ чисел, то вони і є відповіддю на задачу. Інакше, відповіді не існує.

Код розв’язку С++

D. Лікування

У цій задачі потрібно об’єднати всі задані проміжки $[l_i, r_i]$ та вивести суму $k$ перших значень, які належать їм.

Застосуємо метод скануючої прямої. Створимо вектор подій $t$ — відкриття проміжку та закриття. Відкриття відбудеться в момент часу $l_i$, а закриття — в момент $r_i+1$ (тобто права границя береться невключно). Причому для кожної події запам’ятаємо її тип — відкриття або закриття. Посортувавши ці події за зростанням, будемо перебирати від першої до останньої та підтримувати баланс відкритих проміжків (поточна кількість подій відкривання мінус кількість подій закривання). Якщо до події $t_i$ баланс є додатним, це означає, що таблетки з проміжку $[t_i, t_{i+1})$ лікують вірус.

Якщо $k$ перевищує значення $t_{i+1}-t_i$ (кількість таблеток у проміжку), потрібно додати суму всіх цих таблеток до відповіді, а від $k$ відняти їх кількість. У протилежному разі, потрібно лише додати суму перших $k$ та завершити роботу.

Код розв’язку С++

E. Вакцина вiд реп’яховiруса

Необхідно заданий рядок довжини $n$ трансформувати в інший, використовуючи операцію «перенести якийсь символ в кінець рядка». Дозволено використовувати не більше ніж $n$ операцій. Зрозуміло, що для існування відповіді необхідно, щоб кількості відповідних букв в обох рядках співпадали.

Нехай початковий рядок $s = s_0s_1...s_{n-1}$, та кінцевий рядок $t = t_0t_1...t_{n-1}$. Будемо будувати рядок $t$ зліва направо: першою операцією візьмемо символ $t_0$, другою операцією — символ $t_1$ і т. д. Останньою операцією візьмемо останній символ $t_{n-1}$.

На $i$-ому кроці в нас є побудований префікс рядка $t$ довжини $i-1$, та використані деякі символи рядка $s$. Треба серед того, що залишилося в рядку $s$, знайти символ, який відповідає символу $t_i$, і застосувати операцію до нього. Найпростіша реалізація такого розв’язку працює за час $O(n^2)$ та набирає 15 балів з 25 можливих.

Оптимізувати цей розв’язок можна так: для кожної з 26 букв запишемо позиції їх входження в рядок $s$. Кожен символ будемо використовувати справа наліво. Коли беремо якийсь символ, все що треба зробити — пройтися по всіх вказівниках для інших символів і для тих, що є праворуч, запам’ятати, що вони тепер змістилися на одну позицію ліворуч. Така оптимізація перетворює розв’язок у лінійний, тобто $O(n)$.

Код розв’язку С++

F. Реп’яховірус

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

Оскільки за умовою задачі наша швидкість перевищує швидкість інших двох точок, то ми завжди можемо зловити ці дві точки. Можна показати, що завжди буде вигідною така стратегія: спершу ловимо якомога швидше якусь одну точку. Тоді ловимо іншу. Для розв’язку переберемо два варіанти, яку з точок ловити першою.

Тепер задача зводиться до такої: задано нашу початкову точку ($x$, $y$), нашу максимальну швидкість $v$, початкове розміщення точки, яку ми хочемо зловити ($x_0$, $y_0$), та вектор руху цієї точки ($dx$, $dy$). Оскільки ми хочемо зловити точку якомога скоріше, то ми будемо рухатися з максимальною швидкістю до точки, у якій ми зустрінемося із ціллю. Нехай це займе час $t$. Тоді зустріч відбудеться в точці ($x_0 + dx \cdot t$, $y_0 + dy \cdot t$). Умова коректності такої точки є те, що час, за який ми доберемося до неї повинен бути рівно $t$:

$t = \frac{\sqrt{(x_0 + dx \cdot t - x)^2 + (y_0 + dy \cdot t - y)^2}}{v}$

Якщо переписати цю умову, отримаємо квадратне рівняння:

$t^2 \cdot (v^2 - dx^2 - dy^2) - 2 \cdot t \cdot (dx \cdot (x_0 - x) + dy \cdot (y_0 - y)) - (x_0 - x)^2 - (y_0 - y)^2 = 0$

Додатний розв’язок цього рівняння — час, за який ми зловимо точку.

Код розв’язку С++

G. Усе добре

Застосуємо метод динамічного програмування. Підвісимо дерево за довільну вершину-корінь та введемо такий стан динаміки: $[v][mask]$ — скількома способами можна розрізати ребра в піддереві вершини $v$ так, аби утворені компоненти (усі, окрім тої, яка вище за $v$) покривали розміри з масиву $a$, які вибрані в масці $mask$.

Для обчислення відповіді для вершини $v$ та всіх масок (їх буде $2^k$) потрібно ввести допоміжну динаміку по всіх синах вершини $v$. Кожен із синів повинен покривати якусь підмаску, а їх об’єднання має утворити цілу маску. Таку динаміку можна перерахувати за $3^k$ для кожного сина, перебираючи підмаски поточної маски, яку має покривати поточний син.

Після обчислення допоміжної динаміки для синів є дві опції щодо вершини $v$ — або залишити ребро, яке веде до її батька, або видалити його. При цьому для маски, яку покрили сини, можна визначити, яким буде розмір нової утворено компоненти у випадку, коли ребро буде видаленим. Цей розмір повинен бути присутнім серед усіх непокритих значень у масці. Якщо їх декілька, переберемо кожен варіант вибору та виставимо відповідний біт в 1.

У результаті в стані $[root][2^k-1]$ буде записано відповідь. Проте деякі розрізання могли бути пораховані декілька разів. Це відбуватиметься у разі, коли в масиві $a$ були однакові значення. Причому якщо якесь значення повторювалось $c$ разів, то відповідь була домножена на $c!$, оскільки кожен з варіант був обраний рівно один раз. Тому наприкінці для кожного значення масиву $a$ поділимо відповідь на $c!$, де $c$ — кількість входжень цього значення в масив $a$.

Код розв’язку на С++

A. 47-й день року

У задачі необхідно вивести 47-ий день заданого року. Таким днем кожного року є 16 лютого. Відповідно для розв’язку задачі достатньо просто вивести рядок 16.02. і потім номер року, який треба зчитати з вводу.

Код розв’язку C++

B. Свято в магазині

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

Зрозуміло, що неможливо зробити більше ніж $\frac{n-1}{2}$ локальних мінімумів. Тому у випадках, коли $k > \frac{n-1}{2}$, виведемо -1.

Щоб створити локальний мінімум у перестановці, нам достатньо просто поміняти місцями два сусідні числа у зростаючій послідовності. Щоб створити $k$ локальних мінімумів просто зробимо $k$ таких операцій. Наприклад:

$1 2 3 4 5 6 7 \rightarrow 1 \Leftrightarrow 2 3 \Leftrightarrow 4 5 \Leftrightarrow 6 7 \rightarrow 2 1 4 3 6 5 7$

Код розв’язку C++

C. Слоган міста

Очевидно, що аби з рядка $s$ можна було утворити $t$, потрібно аби $t$ був підпослідовністю $s$. Для того щоб це перевірити, достатньо пройти циклом по рядку $t$, підтримуючи вказівник на відповідне входження такого ж символу в $s$. При переході до наступного символу в $t$ потрібно сунути вказівник $s$, допоки не знайдеться відповідний символ. Якщо вказівник прийшов у кінець рядка, і шуканий символ не був знайдений — підпослідовності не існує.

Після того як відомо, чи можна із $s$ утворити $t$, потрібно визначити мінімальну кількість кроків, необхідну для цього. Єдиним обмеженням є той факт, що не можна видаляти більше ніж два однакові символи в межах одного кроку. З цього випливає, що цю кількість можна окремо порахувати для кожної букви, а потім знайти максимальне значення. Зрозуміло, що якщо певну букву потрібно видалити $x$ разів, то кількість кроків для цього — це $\lceil \frac{x}{2} \rceil$ (заокруглене вгору).

Код розв’язку C++

D. Максимальне щастя

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

Задача розв’язується жадібно. Спочатку будемо видаляти четвірки, які є сусідами з хоча б однією сімкою, поки не видалимо всі четвірки (це завжди можна зробити за умови якщо присутня хоча б одна сімка). Потім видалимо всі сімки в такому порядку, щоб кожна сімка, яку ми видаляємо, сусідила з двома іншими сімками. Коректність такого підходу легко бачити, якщо розглянути еквівалентну задачу, у якій замість $4$ і $7$ є $0$ і $1$.

Реалізувати такий алгоритм можна, використовуючи структуру даних стек. Проходимося по послідовності зліва направо й кладемо елементи на стек. Якщо пробуємо поставити $7$ на $4$, то видаляємо $4$. Якщо ставимо $4$ на $7$, то видаляємо $4$ (не ставимо на стек). У результаті залишиться послідовність із сімок, яку треба опрацювати окремо.

Код розв’язку C++

E. Реп’яхи

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

Знайти таку точку дуже просто. У момент дотику відстань між центрами двох кіл рівна сумі їхніх радіусів. Координати $x$ центрів кожного з кіл нам відомі спочатку. За теоремою Піфагора можемо визначити, що $(y-y_i)^2 = (r + r_i)^2 - (x - x_i)^2$. Найбільше значення $y$ і буде шуканою координатою $y$ центра кола, що падає. Варто також звернути увагу на те, що для того, щоб коло зупинилося, відстань між центрами кіл має бути строго меншою за суму їхніх радіусів.

Код розв’язку C++

F. Святковий торт

У задачі задано граф, у якому деякі ребра мають вагу, а деякі — ні. Необхідно зважити всі ребра, щоб найкоротша відстань між першою і останньою вершинами була рівна заданому числу $w$.

У першій підзадачі, яка вартувала 10 балів, усі ребра початково не мали ваги. Для того щоб розв’язати цю підзадачу, достатньо знайти шлях між першою і останньою вершинами, на якому є найменша кількість ребер, наприклад, алгоритмом пошуку вшир (BFS). Нехай ця кількість рівна $k$. Тоді якщо $k > w$, то відповіді не існує. Інакше вона завжди існує і її можна досягнути, наприклад, так: всім ребрам не на найкоротшому шляху дамо вагу $w$, усім ребрам, окрім одного на шляху, дамо 1, а останньому дамо $w - k$. У такий спосіб будь-який шлях, окрім найкоротшого, буде мати вагу не меншу за $w$, а найкоротший буде мати вагу рівно $w$.

Для того щоб розв’язати задачу повністю, спершу зробимо, щоб усі ребра без ваги мали вагу 1. Знайдемо найкоротшу відстань між першою і останньою вершинами, наприклад, алгоритмом Дейкстри. Якщо вона перевищує $w$, то відповіді не існує.

Тепер будемо перебирати всі ребра, які треба зважити, в довільному порядку і для кожного з них повторимо такий процес. Знайдемо найкоротшу відстань між першою і останньою вершиною. Нехай ця відстань рівна $d$. Додамо до ваги поточного ребра значення $w - d$ (це значення завжди буде невід’ємне).

Після того як опрацюємо всі ребра, ще раз знайдемо найкоротшу відстань між першою і останньою вершинами. Якщо вона рівна $w$, то ми знайшли відповідь. Інакше, відповіді не існує.

Код розв’язку C++

G. Ремонтні роботи

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

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

Це зведення означає, що ми виділяємо максимальну кількість точок-розділювачів, через які не можуть проходити ремонтні роботи, в той час як між ними має бути хоча б одна. Зрозуміло, що максимізація цього числа є еквівалентною максимізації кількості проміжків, яку просять в умові.

Таку зведену задачу легко розв’язати методом динамічного програмування. Введемо стан — координата останньої вибраної точки — і для цього стану будемо максимізовувати загальну кількість уже вибраних точок. Для переходу з такого стану переберемо наступну вибрану точку справа від поточної. Залишається лише перевірити, чи коректним є такий перехід, а саме, чи існує хоча б одна компанія між цими точками, а також, чи кожна з них «поміститься» між цими точками.

Код розв’язку C++

A. Перехiд дороги

Задано масив цілих чисел. Треба сказати, скільки є таких індексів $i$, що $a_i$ та $a_{i+1}$ різної парності.

Код розв’язку C++

B. Щасливенькі числа

Задано натуральне число $n$. Треба сказати кількість натуральних чисел, що не перевищують $n$, таких, що їхня сума цифр — щаслива.

Переберемо всі числа від 1 до $n$ і перевіримо, чи сума цифр щаслива.

Код розв’язку C++

C. Покращення середнього балу

Задано масив чисел. Можна видалити деякі з них так, щоб сума чисел, які залишаться, була не меншою за $x$ і середнє арифметичне цих чисел було максимальне.

Ми хочем, щоб $\frac{sum}{count}$ чисел, які залишаться, було максимальним. Припустимо, що в нас фіксований $count$, тоді ми хочем максимізувати суму. Тоді нам достатньо видалити $n-count$ найменших чисел, щоб максимізувати суму.

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

Код розв’язку C++

D. Нерівноправна гра

Марічка й Зеник грають у гру. Є $n$ купок каменів. Марічка ходить першою і може вибрати підмножину купок розміру від 1 до $n-1$ і забрати будь-яку ненульову кількість каменів з кожної із цих купок. Зеник має право забирати будь-яку ненульову кількість каменів тільки з однієї купки. Програє той хто не зможе зробити ходу. Хто виграє при оптимальній грі обох?

Припустим, $n \ge 3$. Марічка може забрати 1 купку першим ходом. Незалежно від ходу Зеника на наступному ході Марічки буде щонайменше $n-2$ купки і не більше ніж $n-1$ купка, тому Марічка зможе забрати їх усіх. Якщо $n = 2$, то Зеник виграє тоді й тільки тоді, коли $a_0 = a_1$. Він зможе завжди повторювати хід Марічки, але в протилежну купку. Інакше виграє Марічка, звівши гру першим ходом до гри, де $a_0 = a_1$

Код розв’язку C++

E. Математична задача

У вас є число $n < 10^9$. Ви можете поділити (якщо ділиться) його на 4 або відняти 7. Треба сказати, чи можна отримати 1.

Розглянемо задачу з іншого боку — ми можем помножити число на 4 й додати 7. Переберем кількість множень на 4. Їх буде не більше ніж $\log_4 n$. Нехай кількість множень — $x$. Наше число — це $4^x$ і тепер ми можемо додати $7 \cdot 4^y$, де $y \le x$. Будем додавати числа жадібно — знаходити таке найбільше $y$, що $7 \cdot 4^y$ в сумі з нашим поточним числом менше або рівне тому числу, яке нам потрібне.

Код розв’язку C++

F. Хімічні експерименти

Вам задано натуральне число $n$, та потрібно сказати яку максимальну кількість елементів можна вибрати з множини $\{1, 2, \ldots, n\}$, так щоб жодні два вибрані елементи не відрізнялись на 4 або 7.

Спершу наведемо приклад розв’язку динамічним програмуванням. Позначимо через $dp[i][mask]$ найбільшу кількість елементів, які ми можемо вибрати з множини $\{1, 2, ..., i\}$, причому маска $mask$ відповідає за те, чи брали ми 7 останніх елементів. З кожного стану є не більше ніж два переходи: ми можемо або взяти поточний елемент (якщо він не конфліктуватиме із жодним з попередніх), або ж пропустити його.

Складність такого алгоритму: $O(n \cdot 2^7)$ по часу та пам’яті, що проходитиме 80% тестів, втім його можна оптимізувати до $O(n)$ по пам’яті, тримаючи динаміку пошарово, хоч це й доволі складно реалізовувати.

Код розв’язку C++

Другий розв’язок конструктивний. Розглянемо групу з 11 елементів, що йдуть підряд. Можна показати (або на папері, або програмно згенерувати попереднім розв’язком), що з них не можна вибрати більше ніж 5 елементів, що не конфліктуватимуть між собою. Причому саме 5 елементів можна вибрати, наприклад, узявши набори $\{1, 3, 4, 6, 9\}$ чи $\{1, 2, 4, 7, 10\}$. Тепер будуватимемо відповідь так: розіб’ємо множинну $\{1, 2, \ldots, n\}$ на блоки по 11 чисел у кожному (можливо, менше в останньому). Ясно, що з кожного блоку ми можемо взяти не більше ніж 5 чисел. Розглянувши кілька простих випадків, бачимо, що якщо остача $n$ за модулем 11 рівна 2, то можна в кожній групі вибирати елементи з множини остач $\{1, 2, 4, 7, 10\}$, а в інших випадках — з множини $\{1, 3, 4, 6, 9\}$. Формальне доведення залишаємо вам на домашнє завдання :)

Складність такого розв’язку: $O(n)$ по часу та $O(1)$ по пам’яті.

Код розв’язку C++

G. Фізичні експерименти

Вам задано $n$ ламп, кожна початково може бути або вимкненою, або ввімкненою. Вам потрібно зробити рівно $n$ ходів, на $i$-ому з них ви вибираєте рівно $i$ ламп та змінюєте їхній стан на протилежний. Чи можна вимкнути всі лампи?

Як і в попередній задачі, опишемо два розв’язки — конструктивний та за допомогою динамічного програмування.

Спершу розв’язок динамічним програмуванням. Нехай $dp[i][j]$ — це кількість ламп, які треба було вимкнути на $і$-ому кроці, щоб після нього рівно $j$ ламп були ввімкнені. Зауважимо, що таких можливих кількостей може бути декілька. У такому разі $dp[i][j]$ — будь-яка з них. Якщо ж після $i$-ого кроку взагалі неможливо мати рівно $j$ ввімкнених ламп, то в $dp[i][j]$ триматимемо відповідну мітку (наприклад, -1).

Якщо після $i$-ого кроку в нас рівно $j$ увімкнених ламп і на $(i + 1)$-ому кроці ми вимикаємо $k$ ламп, то вмикаємо $(i + 1 - k)$ ламп. Тоді кількість ввімкнених ламп стане $(j - k + i + 1 - k)$. Тобто, якщо в стан $dp[i][j]$ можливо перейти, то можна оновити $dp[i + 1][j - k + i + 1 - k]$ значенням $k$. Якщо в стан $dp[n][0]$ неможливо прийти, то відповідь — No. Інакше — Yes. Для кожного стану ми знаємо, скільки ламп треба було вимкнути на попередньому кроці, і можемо симулювати процес. Складність: $O(n^3)$ часу та $O(n^2)$ пам’яті.

Конструктивний розв’язок. Покажемо, що з початкового стану ми завжди можемо перейти в стан, де всі (крім, можливо, однієї) лампи є вимкнутими. Спочатку зауважимо, що порядок ходів не має значення, тому робитимемо спочатку $n$ перемикань, потім $n - 1$ і так далі. Підтримуватимемо такий інваріант: після ходу з $і$ перемиканнями є не більше за $i$ ввімкнених ламп. Спочатку таке, звісно ж, виконується. На кожному кроці будемо в першу чергу вимикати всі ввімкненні лампи, а в другу — вмикати вимкнуті. Якщо на якомусь кроці ми маємо змінити стан $i$ ламп, причому на його початку було не більше ніж $i + 1$ ввімкнута лампа, то таким процесом ми залишимо не більше за $і$ ввімкнутих ламп.

Тепер покажемо, що з ніякого стану ми не можемо перейти якимись ходами в стан, де всі лампи вимкнуті, а якимись іншими — де всі, крім рівно однієї, вимкнуті. Це зрозуміло з міркувань парності, адже парності кількостей перемикань всіх ламп у цих двох кінцевих станах відрізняються, що неможливо з огляду на те, що сума перемикань для досягнення кожного з них є однаковою, а саме $1 + 2 + \ldots + n = \frac{n \cdot (n + 1)}{2}$, де $n$ — початкова кількість ламп.

Тому ми виконуватимемо процес, описаний у першій частині, і якщо в кінцевому стані всі лампи вимкнені, то це і є розв’язок, інакше — розв’язку не існує.

Складність такого розв’язку: $O(n^2)$ часу та пам’яті.

Код розв’язку C++

A. Скільки заплатити?

Задано два цілі числа. Треба вивести третє, таке що одне з двох чисел не вході є меншим за третє, а інше — більше.

Якщо $|a-b| \le 1$, то таке зробити неможливо. Інакше відповідь існує. Наприклад, завжди підходить число $min\{a, b\} + 1$.

Код розв’язку C++

B. Котик та рядок символів

Задано рядок символів. Потрібно сказати, скільки символів треба вставити в рядок, щоб жодні два символи підряд не були однаковими.

Щоб два однакові символи підряд перестали бути двома однаковими символами підряд, достатньо вставити поміж них будь-який інший символ. Тому відповідь — кількість пар однакових символів підряд.

Код розв’язку C++

C. Картопля в підвалі

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

У задачі є багато можливих розв’язків. Наприклад, можна йти по рядках знизу вверх, по кожному рядку справа наліво й повністю забирати всі кубики з клітинок у такому порядку. Легко бачити, що при такому порядку забирання кубиків необхідна умова завжди буде підтримуватися.

Код розв’язку C++

D. Поділ котів

Задано набір з $n$ чисел, кожне з яких від 1 до 4. Потрібно розбити цю множину на дві з однаковою сумою.

Очевидно, для кожної з можливих ваг $(1..4)$ нас цікавить, скільки котів з такою вагою припаде Зенику. Тому достатньо перебрати всі четвірки чисел $(c_1, c_2, c_3, c_3)$, які позначають, скільки котів певної ваги отримає Зеник. Якщо існує четвірка, для якої $1 \cdot c_1 + 2 \cdot c_2 + 3 \cdot c_3 + 4 \cdot c_4 = \frac{s}{2}$ — розділити котів можна, інакше — ні (тут $s$ — загальна вага всіх котів).

Код розв’язку C++

E. Поповнення в сім’ї

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

Зрозуміло, що з масиву видаляться всі такі елементи, що десь праворуч від них є більший елемент, а всі решта залишаться. Тому будемо йти справа наліво і підтримувати максимум на суфіксі. Якщо поточне число менше за максимум, то воно видалиться. Інакше воно увійде в результуючу послідовність.

Код розв’язку C++

F. Кухня та котик

Задано розміри прямокутника, який треба покрити плиткою $2 \times 1$. Одну з клітинок покривати не можна. Потрібно сказати, чи можна покрити всі клітинки, крім заданої. Якщо так — вивести розбиття.

Неважко побачити, що коли $n$ або $m$ є парними, то відповіді не існує. Адже в такому разі загальна кількість клітинок, які потрібно покрити, є непарною, тому це неможливо.

Коли $n$ та $m$ є непарними, покриття все ще може бути неможливим (другий тест з умови). Розфарбуємо прямокутник у шаховому порядку. Причому пофарбуємо верхню ліву клітинку в білий колір. У такому разі білих клітинок на одну більше, ніж чорних. Оскільки одна плитка покриває одну білу та одну чорну клітинки — нам потрібно, щоб кіт спав на білій. Клітинка біла, якщо $x+y$ — парне число.

Якщо ж $n$ та $m$ є непарними, а $x+y$ — парним, прямокутник можна розфарбовувати так. Неважко з правої сторони відрізати смужку довжиною 2:

(Так само можна відрізати смужку розміром 4, 6, 8, ..., тобто будь-яку парну довжину.)

Аналогічно по інших сторонах:

Після цього або вся площа буде закладеною, або ж залишиться квадрат $3 \times 3$, усередині якого є виділена клітинка. Такий квадрат легко розфарбувати — достатньо розкласти 4 плитки «по колу» від виділеної клітинки.

Код розв’язку C++

G. Котомережа

Задано дерево, у якому $k$ вершин є позначеними. Потрібно розбити ці вершини на пари так, щоб не було двох пар, для яких шляхи між вершинами перетинаються.

Підвісимо дерево за довільну вершину. Знайдемо найнижчу вершину, для якої кількість позначених вершин у піддереві (включно з нею) більша за один. Тоді зрозуміло, що якщо кількість для цієї вершини є більшою за два, то відповіді не існує, адже хоча б два шляхи точно будуть проходити через цю вершину. Якщо ж ця кількість є рівною 2, то спаруємо ці вершини та видалимо їхні позначення. Цей процес потрібно повторювати, допоки залишаються позначені вершини.

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

Код розв’язку C++

A. Знижка вiд уряду

Порахуємо ціну за дві пачки гречки без знижки — $2 \cdot a$, а зі знижкою — $b$. Отже, ми зекономимо $2 \cdot a - b$.

Код розв’язку C++

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

B. Степан на карантині

Пройдемо циклом по всіх областях, і якщо кількість хворих у відповідній області більша за межу «червоної» зони, тоді до відповіді додаємо одиницю.

Код розв’язку C++

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

C. Золотий злиток

Нехай $p_i$-е ребро злитка лежить уздовж $i$-ого ребра валізи. Тоді для всіх $i$ має виконуватися $a_{p_i} \le b_i$. Переберемо всі можливі перестановки $p$ та перевіримо, чи виконується ця умова хоча б для однієї з них.

Код розв’язку C++

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

D. Шифрування корупційних схем

Достатньо реалізувати алгоритм, описаний в умові — для кожної серії знайдемо її довжину, виведемо її розмір та сам символ.

Код розв’язку C++

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

E. Дешифрування корупційних схем

У рядку виділимо числа — довжини серій та літери — символи рядка. Кожен символ виведемо потрібну кількість разів.

Код розв’язку C++

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

F. Довідки

Використаємо підхід динамічного програмування, а саме $dp_i$ — максимальна відстань, яку Зенику потрібно буде пройти, за умови, що він має всі довідки від 1 до $a_i$ і стоїть у кабінеті $i$. Тоді перебравши наступний кабінет, у який завітає Зеник, можна порахувати відповідь для позиції $i$. Складність такого підходу — $O(n^2)$.

Можна показати, що для того, щоб максимізувати відстань, яку пройде Зеник, його варто відправити в крайній кабінет, який видає поточну довідку. Наприклад, якщо він зараз у кабінеті, де видають 2-гу довідку, тоді його відправлять або в найлівіший, або в найправіший кабінет, у якому видають 3-тю довідку. Складність у такому разі стає $O(n)$.

Код розв’язку C++

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

G. Велике крадівництво

Використаємо систему неперетинних множин.

Пройдемся по всіх ребрах графа $(u, v)$. Якщо вершини $u$ та $v$ належать різним компонентам зв’язності, то просто об’єднаємо їх. Якщо ж вони в одній компоненті, назвемо це ребро зайвим.

Пройдемося по всіх зайвих ребрах $(u, v)$. Якщо в графі є тільки одна компонента зв’язності, то задача розв’язана. Інакше, існує вершина $w$, що не зв’язна з $u$. Замінимо дорогу $(u, v)$ на $(u, w)$ та об’єднаємо компоненти, що містять вершини $u$ й $w$.

Зауважте, що оскільки $m \ge n$, відповідь завжди існує.

Код розв’язку C++

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

A. Задача про задачі

Розглянемо всі варіанти вибору Василем двох задач:

перша й друга задачі;
перша й третя задачі;
друга й третя задачі.

Якщо хоча б в одному варіанті сума складностей не перевищує 47, тоді відповідь YES, якщо ж ні, то відповідь — NO.

Код розв’язку C++

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

B. Великий бенкет

Оптимальним розливанням соку буде таке:

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

Код розв’язку C++

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

C. Запорожець-лімузин

Порахуємо кількість ям, у яких глибина строго більша ніж $k$. Нехай їхня кількість — $y$. За умовою водій може об’їхати $x$ ям, а досягти точки призначення за умови, якщо відвалилося не більше ніж одне колесо. Отже, якщо $x - y \ge -1$, то відповідь YES, інакше — NO.

Код розв’язку C++

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

D. Піца

Спочатку для зручності подвоїмо масив. Порахуємо кількість оливок від першого до $\frac{n}{2}$-го куска включно. Зазначимо, що для того, щоб дізнатися кількість оливок від другого до $(\frac{n}{2}+1)$-го шматка, нам достатньо відняти 1 оливку від теперішньої кількості, якщо вона була на першому шматку, та додати 1 оливку, якщо вона є на $(\frac{n}{2}+1)$-му шматку. Отже, за один прохід ми можемо порахувати кількість оливок на всіх можливих розділеннях піци. І серед усіх розділень піци взяти те, де є мінімальна можлива кількість оливок.

Код розв’язку C++

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

E. Сік

Переберемо довжину одного з крайніх відрізків, наприклад, правого. Нехай сума всіх елементів із цього відрізка рівна $x$, а сума всіх інших елементів — $2 \cdot s$. Доведемо, що для зафіксованого правого відрізка (його розміру), ту частину масиву, яка не входить у правий відрізок, оптимально поділити так, щоб модуль різниці цих двох відрізків був мінімально можливим.

Нехай ми розділили решту масиву на дві половини із сумами $a$ й $b$. Без обмежень загальності поставимо $a \le b$ та $2 \cdot y = b - a$ Тоді $a + b = s$, $a = s - y$, $b = s + y$.

Тепер розглянемо три випадки взаємного розташування $x$, $a$ й $b$:

$x \le a \le b$ — тоді відповідь рівна $b - x = s - x + y$;
$a \le x \le b$ — тоді відповідь рівна $b - a = 2 \cdot y$;
$a \le b \le x$ — тоді відповідь рівна $x - a = x - s + y$.

У цих випадках $s$ та $x$ є константами для зафіксованого правого відрізка. У кожному з них для того, щоб мінімізувати відповідь, потрібно мінімізувати $y$.

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

Код розв’язку C++

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

F. Реєстрація

Зауважимо такий факт: якщо ми можемо зареєструвати всіх учасників за деякий час $t$, то ми можемо зареєструвати всіх учасників і за час $t + 1$. Скористаємось ідеєю бінарного пошуку по відповіді. Для цього попередньо відсортуємо за зростанням масив координат організаторів $a$ та масив координат команд $b$. Зафіксуємо якийсь час $t$ та перевіримо, чи можливо за цей час зареєструвати всі команди. Для цього переберемо по черзі кожного організатора та будемо підтримувати вказівник на останню команду, яку може зареєструвати цей організатор, витративши час не більший за $t$. Якщо вдасться зареєструвати всі команди, то змінимо праву границю для нашого бінарного пошуку, а якщо ні — ліву.

Код розв’язку C++

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

G. Кольорові карти

Якщо $k = 1$, тоді існує єдине розбиття числа $n$ на степені двійки — двійкове представлення числа.

Нехай ми знаємо розбиття $n$ на $a_1, \ldots, a_k$, де $a_i$ позначає суму карт із кольором $i$. Кожне таке розбиття відповідає єдиному набору карт, і кожен набір карт відповідає єдиному такому розбиттю, а отже кількість наборів карт, що в сумі дають $n$ рівна кількості розбиттів $n$ на $a_1, \ldots, a_k$. А кількість таких розбиттів — це кількість комбінацій з повтореннями (детальніше про це можна прочитати за посиланням ). Тож кількість комбінацій з повторами рівна $C_{n+k-1}^{k-1}$ — біноміальному коефіцієнтові, який можна порахувати за заданим модулем багатьма способами.

Код розв’язку C++

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

A. Хелловін

Виведемо суму цін найдешевших цукерок з кожного мішка.

Код розв’язку C++

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

B.Кольорові кульки

Якщо $a > b$, поміняємо $a$ й $b$, G й Y. Без обмеження загальності вважаємо, що $a \le b$. Виведемо $b-a$ разів G, потім — $a$ разів YG.

Код розв’язку C++

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

C. Нова кухня

Якщо $n$ і $m$ — непарні, то площа кухні також непарна, тому не вийде замостити всю підлогу. Нехай тепер хоча б одне із чисел $n$ і $m$ парне. Якщо $m$ непарне, то замостимо підлогу вертикальними плитами, якщо ж парне — горизонтальними.

Код розв’язку C++

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

D. Знайди паліндром

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

Паліндром парної довжини має два однакові центральні символи, а не один. Цей випадок розглядається так само.

Складність розв’язку: $O(n^2)$.

Код розв’язку C++

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

A. Непередбачувана погода

Проітеруємося по днях, і якщо відповідний день має додатну середню температуру повітря, то виведемо його номер.

Код розв’язку C++

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

B. Загадкове число

Для того, щоб отримати мінімально можливе число, потрібно на кожну позицію поставити мінімально можливу цифру, тобто 0. Проте якщо це перша цифра числа, тоді потрібно поставити 1, бо число не може починатися з 0. Для максимального числа потрібно поставити всюди максимальну цифру, тобто 9.

Код розв’язку C++

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

C. Незростаюча послідовність

Нам ніколи не вигідно міняти одне число більше ніж один раз, тому що ми можемо за одну операцію поміняти його на його кінцеве значення. Отже, мінімальна кількість змін рівна $n$ мінус максимальна кількість елементів, що залишаться незмінними. Нескладно переконатися, що Зеник не може одночасно залишити незмінними числа $a$ й $b$, якщо вони різні, тобто він може залишити незмінними тільки однакові елементи. А отже нам потрібно знайти максимальну кількість однакових елементів і тоді від $n$ відняти цю кількість.

Код розв’язку C++

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

D. Підрядки-перестановки

Перестановка довжини $i$ повинна містити лише числа від 1 до $i$. Для кожного $i$ від 1 до $n$ розглянемо перші $i$ чисел і подивимося, чи ці числа утворюють послідовний відрізок.

Нехай $l_i$ — найлівіша позиція серед перших $i$ чисел, а $r_i$ — найправіша. Це означає, що елементи від 1 до $i$ є на проміжку $[l_i, r_i]$. Цей проміжок буде перестановкою тоді й лише тоді, коли він містить лише елементи від 1 до $i$.

Ми знаємо, що ці елементи там містяться, але необхідно ще забезпечити умову того, що там немає інших елементів. Ця умова рівносильна тому, що на цьому відрізку є рівно $i$ елементів. Більш формально, якщо $r_i - l_i + 1 = i$, тоді цей відрізок не містить зайвих елементів і є перестановкою.

Тобто нам достатньо пройтися по всіх $i$ й для відповідного $i$ знайти $l_i$ та $r_i$. Це нескладно зробити, знаючи $l_{i - 1}$ і $r_{i - 1}$. Тепер для кожного $i$ виконаєм перевірку чи $[l_i, r_i]$ є перестановкою.

Код розв’язку C++

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

A. Гра в карти

Паліндром парної довжини має вигляд $s+r$, а непарної — $s+c+r$, де $s$ — деякий рядок, $r$ — розвернутий $s$, $c$ — деякий символ.

Кожен символ зустрічається однакову кількість разів в $s$ і $r$. Якщо символ зустрічається на $a$ картах, то додамо його $\left\lfloor \frac{a}{2} \right\rfloor$ входжень до рядка $s$. Якщо існує символ $c$, який зустрічається на непарній кількості карт, то виведемо паліндром $s+c+r$, інакше — $s+r$.

Код розв’язку C++

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

B. Земля й Місяць

Спершу треба розглянути тривіальні випадки: круги не перетинаються або один круг міститься в іншому.

На рисунках зображені варіанти розташування кіл. Застосувавши теорему косинусів до трикутника $O_1AO_2$, отримаємо $r_2^2=d^2+r_1^2-2 d r_1 \cos \alpha_1$, $r_1^2=d^2+r_2^2-2 d r_2 \cos \alpha_2$. Звідси можемо знайти кути $\alpha_1$ і $\alpha_2$.

Площа перетину кругів — це сума площ двох сегментів. Центральний кут сегмента першого круга — $\angle AO_1B=2\alpha_1$, площа цього сегмента — $\left(\alpha_1 - \frac{\sin 2 \alpha_1}{2}\right)r_1^2$ (формула для площі сегмента з Вікіпедії). Площу іншого сегмента знаходимо так само.

Код розв’язку C++

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

C. Сходи до Місяця

Скористаємося підходом динамічного програмування. Якщо ви не знаєте, що це, то радимо прослухати відеолекцію.

Станом динаміки $dp$ є трійка чисел $(i, mn, mx)$, де $i$ — скільки сходинок уже подолав Зеник, $mn$ і $mx$ — найкоротший і найдовший кроки. Значенням динаміки є кількість способів потрапити в такий стан.

Ініціалізуємо значення $dp[i][i][i] = 1$ — Зеник зробив один крок на $i$ сходинок. Зі стану $(i, mn, mx)$ є переходи в стани $(i+j, \min\{mn, j\}, \max\{mx, j\})$, де $j$ — довжина нового кроку.

Відповіддю на задачу буде сума $dp[n][mn][mx]$ для всіх $mn, mx$, що задовольняють умову $mx - mn \le k$.

Складність розв’язку: $O(n^4)$.

Код розв’язку C++

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

D. Гра на прямiй

Нехай $s_i=\sum_{j=1}^{i-1} a_j$. Пересунути фішку з позиції $x$ у позицію $y$ коштує $|s_y-s_x|$.

Тепер задачу можна переформулювати так. Задано $n$ точок на прямій, $i$-а точка має координату $s_i$. Починаємо з точки $s_1=0$. Хочемо відвідати всі та мінімізувати відстань, яку пройдемо.

Очевидно, що оптимально піти до найлівішої точки, потім — до найправішої, або навпаки.

Складність розв’язку: $O(n)$.

Код розв’язку C++

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

A. Школяр з Коломиї

Якщо оцінка за предмет — 10 або більше, то вона вже є відмінною. Якщо ж оцінка — 9 або менше, то для того щоб зробити її відмінною, треба буде заплатити $10 - p_i$ доларів. Зрозуміло, що вигідно зробити відмінними спершу всі 9, потім всі 8 і т. д.

Для кожної оцінки від 1 до 12 знайдемо кількість предметів з такою оцінкою. Оцінки 10, 11 і 12 відмінні зразу. Решту оцінок переберемо від 9 до 1. Поки залишаються гроші, будемо робити оцінки з предметів відмінними.

Код розв’язку C++

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

B. Зеник і рядок

Для кожного символа виберемо, на яких позиціях ми будемо його залишати: на парних чи на непарних. Переберемо всі такі варіанти. Для кожного символа є по 2 варіанти, тому загалом різних комбінацій є $2 ^ 4 = 16$. Для кожної комбінації пройдемося по рядку, залишимо відповідні символи й перевіримо, чи збігається отриманий рядок з рядком $t$. Якщо одна з комбінацій підійде, то відповідь позитивна, інакше — негативна.

Код розв’язку C++

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

C. Провальне ЗНО

Для кожного кадета порахуємо дві величини: за яку мінімальну ціну можна виштовхати всіх кадетів ліворуч від нього — $l_i$, і праворуч від нього — $r_i$, відповідно.

Розглянемо кадетів зліва від $i$-ого, які виштовхують когось. Нехай їхні індекси — $i_1, i_2, \ldots, i_l=i$. Тоді $i_1$-ий кадет виштовхує всіх на півінтервалі $\left[1, i_1\right)$, $i_2$-ий виштовхує всіх на $\left[i_1, i_2\right)$ і т. д. Нехай для деякого $j$ $a_{i_j} \ge a_{i_{j+1}}$. Відповідь не стане гіршою, якщо $i_{j+1}$-ий кадет виштовхає всіх, кого виштовхував $i_j$-ий, а $i_j$ не буде виштовхувати нікого. Тому існує оптимальна відповідь, у якій $a_{i_1} < a{i_2} < \dots < a{i_l}$.

Пройдемося по кадетах зліва направо й будемо підтримувати зростаючий стек і рахувати $l_i$. Поки стек непорожній і останній елемент стеку не менший за поточне значення $a_i$, «викидаємо» елемент зі стеку й перераховуємо $l_i$. Після цього «закидаємо» $a_i$ в стек і перераховуємо $l_i$. $r_i$ рахуємо аналогічно до $l_i$.

Для того щоб порахувати відповідь, переберемо, який підвідрізок з $k$ кадетів залишиться наприкінці. Таких варіантів буде $n - k+1$. Для фіксованого початку підвідрізка $i$ нам потрібно виштовхати всіх кадетів лівіше від $i$-ого та всіх кадетів правіше від $(i + k - 1)$-ого, а отже відповідь для $i$ буде рівна $l_i + r_{i+k-1}$. Візьмемо мінімальну відповідь.

Код розв’язку C++

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

D. Проста задача

Спершу скоротимо дріб, поділивши чисельник і знаменник на їхній найбільший спільний дільник. Оскільки відношення суми червоних до суми чорних рівне $\frac{p}{q}$, то сума червоних $r = p \cdot x$, а сума чорних $b = q \cdot x$, де $x$ — ціле. Якщо додамо ці дві суми, отримаємо $(p + q) \cdot x$, а з іншого боку, сума чисел від 1 до $n$ рівна $\frac{n \cdot(n+1)}{2}$. А отже, нам необхідне $n$ таке, що $\frac{n \cdot(n+1)}{2}$ ділиться на $p + q$.

Знайдемо таке мінімальне $n$, для якого це виконується. Воно не є більшим за $2\cdot(p + q)$, бо для $n = 2\cdot(p + q)$ ця умова виконується. Отже, ми можемо визначити $x$, а знаючи $x$ можемо визначити $r$ і $b$.

Методом математичної індукції можна довести, що числами від 1 до $n$ можна подати будь-яку суму від 0 до $\frac{n \cdot(n+1)}{2}$, а отже можна й подати суму рівну $r$. Для цього можна брати якомога більше число серед тих, що ми ще не взяли, і таке, щоб загальна сума не перевищила шукану суму.

Код розв’язку C++

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

E. Запити між серверами

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

Для кожного питання Зеника ми вже знаємо, за який мінімальний час з $x_i$-ої компанії ми можемо надіслати запит на сервер $y_i$. Залишається перевірити, чи цей час не більший за $t_i$.

Код розв’язку C++

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

F. Петрик руйнує міста

Між двома містами $i$ та $j$ можна передати повідомлення, якщо відрізки $[x_i-w_i, x_i+w_i]$ та $[x_j-w_j, x_j+w_j]$ перетинаються або дотикаються. Отже, якщо розглянути такі відрізки, то нам потрібно видалити мінімальну їх кількість, щоб відрізки що залишилися не перетиналися — це рівносильно тому, щоб вибрати максимальну кількість відрізків, що не перетинаються.

Розглянемо найлівіший відрізок, який ми залишили у відповіді. Якщо існує відрізок з меншим правим кінцем, то можна взяти його до відповіді замість того, який зараз найлівіший.

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

Код розв’язку C++

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

G. Дерево

Нехай $len$ — сумарна довжина шляхів. Тоді розділимо шляхи на дві групи:

ті, у яких довжина більша за $B$, таких відрізків буде не більше $\frac{len}{B}$ — назвемо їх великими;
ті, у яких довжина менша за $B$ — відповідно назвемо їх малими.

Для $i$-того великого шляху порахуємо скільки спільних вершин він має з $j$-тим шляхом, позначимо цю величину $cnt_{ij}$. Для $i$-того великого шляху будемо пам’ятати величину, яку ми маємо додати до всіх вершин на ньому — $add_i$. Також будемо пам’ятати суму всіх елементів цього шляху $sum_i$. Для кожної вершини $v$ будемо пам’ятати її поточне значення, не враховуючи оновлень великих шляхів, $x_v$.

Тоді відповідь для $i$-того великого шляху буде рівна $sum_i$ — складність $O(1)$.

Для $j$-того малого шляху порахуємо суму значень $x_v$ вершин цього шляху. Щоб знайти суму на ньому, необхідно ще врахувати ті значення, що додають великі відрізки: $i$-тий великий відрізок додасть $cnt_{ij} \cdot add_i$. Складність рівна $O(B + \frac{len}{B})$, адже потрібно пройтися по всіх вершинах шляху (не більше ніж $B$) і по кожному великому шляху, а великих шляхів не більше ніж $\frac{len}{B}$.

Тепер нам потрібно порахувати значення $cnt_{ij}$ і вміти підтримувати параметри $x_v$ i $sum_i$.

Для $i$-того великого шляху позначимо всі його вершини, тоді переберемо $j$-тий шлях і проітеруємося по його вершинах, і якщо вершина помічена, тоді виконаємо $cnt_{ij} := cnt_{ij} + 1$.

Якщо приходить $+ val$ до $j$-того шляху тоді для $i$-того великого шляху зробимо $sum_i := sum_i + cnt_{ij} \cdot val$. Якщо $i$-ий шлях великий, тоді нам треба ще оновити $add_i := add_i + val$. Якщо ж малий, тоді потрібно пройтися по всіх його вершинах $v$ і виконати $x_v := x_v + val$. Складність — $O(\frac{len}{B}$ i $O(\frac{len}{B} + B)$ для великого і малого шляху відповідно.

Отже, складність для одного запиту рівна $O(\frac{len}{B} + B)$, сумарна складність рівна $O(k \cdot (\frac{len}{B} + B) + n \cdot B)$. Якщо вибрати $B^2 = len$ тоді загальна складність $O((n + k) \cdot \sqrt {len})$.

Код розв’язку C++

A. Апельсини

Перевіримо, чи $a+b>c$.

Код розв’язку C++

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

B. Дедлайн

Кількість кожного дня тижня буде хоча б $\left \lfloor \frac{n}{7} \right \rfloor$, бо до дедлайну пройде стільки повних тижнів. Крім цього, до $n \% 7$ (остача від ділення) днів від сьогодні додамо одиницю.

Код розв’язку C++

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

C. Робот

Для того щоб робот міг потрапити в точку $(x, y)$ необхідно й досить, щоб кількість символів R була хоча б $x$, а кількість U — хоча б $y$. Тоді можна поставити ці символи на початок рядка, і після $x+y$ команд робот опиниться в точці $(x, y)$.

Код розв’язку C++

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

D. Патріотична стрічка

Є два варіанти кінцевої стрічки: або вона починається синьою частиною, або жовтою. Колір першої частини однозначно визначає всю стрічку, тому що кольори повинні чергуватися. Переберемо, який із цих двох варіантів буде кінцевим, і для кожного знайдемо кількість частин, колір яких треба змінити. Виведемо мінімальне значення.

Код розв’язку C++

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

A. Дзідзьо і його пісня

Відповідь дорівнює кількості суцільних відрізків з однакових символів. Така кількість відрізків рівна $n$ - (кількість сусідніх пар однакових символів).

Код розв’язку C++

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

B. Дзідзьо й вівці

Переберемо всі пари стад блакитного й жовтого кольорів, знайдемо площу перетину їхніх прямокутників. Виведемо пару, для якої площа перетину максимальна.

Код розв’язку C++

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

C. Дзідзьо й планета Олімпія

Якщо НСК$(a, b) = x$, то $a$ й $b$ є дільниками $x$. Переберемо всі пари дільників $(a, b)$ та перевіримо, чи найменше спільне кратне цих чисел дорівнює $x$.

Більше про дільники можна дізнатися в цьому відео, а про НСК — у цьому.

Код розв’язку C++

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

D. Дзідзьо й зустріч з фанатами

Нехай, без обмеження загальності, $n \le m$. Якщо $n=1$ і $m$ непарне, то відповідь — 3. Якщо $n=1$ і $m$ парне, то відповідь — 2. Якщо $n>1$, то відповідь — 0. Для кращого розуміння дивіться рис. 1.

Код розв’язку C++

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

A. Пароль

Довжина найбільшого числа — $\left \lceil \frac{n}{k} \right \rceil$.

Будемо будувати найбільше число зліва направо. При цьому підтримуватимемо $c$ — кількість чисел, які ще можуть бути найбільшим. Початково $c$ — кількість чисел завдовжки $\left \lceil \frac{n}{k} \right \rceil$. $c = n \% k$, якщо це значення ненульове, інакше $c=k$.

$\left \lceil \frac{n}{k} \right \rceil$ разів треба дописати до поточного найбільшого числа якомога меншу цифру. Маємо $c$ чисел, які поки що є найбільшими. Візьмемо $c$ найменших невикористаних цифр. Допишемо їх до цих найбільших чисел. Нехай найбільша цифра, яку ми щойно використали — $d$, і ми використали її $c'$ разів. $c'$ буде новим значенням $c$. Виведемо цифру $d$.

Код розв’язку C++

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

B. Кирило Кожум’яка

Якщо Кирило першим ходом узяв паличку завдовжки $a_i$, то Змій повинен узяти паличку завдовжки $a_j$, щоб незалежно від того, яку третю паличку завдовжки $a_k$ вибере Кирило, з них можна було скласти невироджений трикутник. Для всіх $k \ne i, k \ne j$ повинні виконуватися нерівності трикутника: $a_i < a_j + a_k, a_j < a_k + a_i, a_k < a_i + a_j$. Перепишемо ці нерівності так: \[a_j > a_i - a_k, a_j > a_k - a_i, a_j < a_k + a_i.\]

Нехай найкоротша паличка, крім $i$-ої, має довжину $a_{min}$, а найдовша — $a_{max}$. Перевіримо, чи існує таке $j$, що \[a_j > a_i - a_{min}, a_j > a_{max} - a_i, a_j < a_{min} + a_i.\] Якщо існує, то таке $j$ і буде виграшним ходом для Змія.

Нерівності $(1)$ мають виконуватися для $k \ne j$, а в перевірці ми цього не забезпечуємо й маємо сильнішу умову $(2)$. Можна просто окремо перевірити, чи виграє Змій якщо візьме паличку $a_{min}$ чи $a_{max}$.

Однак можна показати, що цих додаткових перевірок не потрібно. Для цього достатньо довести такі дві леми.

Якщо Змій може виграти, взявши паличку $a_{min}$, то він може виграти, взявши паличку $a_{max}$.
Якщо Змій може виграти, взявши паличку $a_{max}$, то для неї будуть виконуватися нерівності $(2)$.

Доведення залишаємо вправою.

Код розв’язку C++

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

C. Трава

Скористаємося підходом динамічного програмування. Детальніше про динамічне програмування можна дізнатися у відео.

Нехай $dp[i][j][c]$ — мінімальна кількість клітинок, яку повинна подолати Коза, щоб опинитися в клітинці $(i, j)$, відвідавши $c$ клітинок з травою. Зі стану $(i, j, c)$ є перехід у стан $(i+1, j, c)$, якщо в клітинці $(i+1, j)$ нема трави, і в стан $(i+1, j, c + 1)$ в іншому разі. Так само є переходи в клітинку $(i, j+1)$.

Відповіддю на задачу є $\min_{i, j} dp[i][j][k]$.

Код розв’язку C++

D. Колобок: факти та фікції

Для кожного запиту будемо підтримувати кінці шляху $a$, $b$. Початково це дві перші вершини шляху.

Розглядаємо відвідану Колобком вершину $p$.

Якщо $p$ лежить на шляху від $a$ до $b$, то нічого не порушується, у цьому разі нічого не робимо.
Якщо $b$ лежить на шляху від $a$ до $p$, то $p$ стає новим кінцем шляху, присвоюємо $b:=p$.
Якщо ж $a$ лежить на шляху від $b$ до $p$, то аналогічно $a:=p$.
Якщо не виконується жодна з трьох вищенаведених умов, то Колобок не міг відвідати на одному шляху вершини $a$, $b$ й $p$. У цьому разі виведемо Ni.

Якщо ми розглянули всі вершини й не вивели Ni, то Колобок міг їх відвідати. Тоді виведемо Tak.

Залишилося навчитися перевіряти, чи лежить деяка вершина $x$ на шляху від $a$ до $b$. Підвісимо дерево за довільну вершину. Нехай $c$ — найменший спільний предок вершин $a$ й $b$. Критерій того, що $x$ лежить на шляху від $a$ до $b$ — $c$ є предком $x$ і ($x$ є предком $a$ або $x$ є предком $b$).

Код розв’язку C++

A. Існує дві дороги: Одна пряма, а інша …

Для кожної дільниці та відповідного їй регіонального представництва порахуємо відстань між ними за теоремою Піфагора: \[\sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}\]

Відповідь рівна сумі всіх цих відстаней.

Код розв’язку C++

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

B. Підрахунок голосів

Якщо існує урна, в якій більше ніж $k$ бюлетенів, то відповідь -1. Інакше знайдемо мінімальну кількість членів комісії $cnt$, якої достатньо для опрацювання всіх урн.

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

Відповідь рівна $n - cnt$ якщо $cnt \le n$, або ж -1, якщо $cnt > n$.

Код розв’язку C++

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

C. Спостерігачі

Час в форматі $hh:mm:ss$ можна перетворити в номер секунди від початку доби за формулою \[t = hh \cdot 60 \cdot 60 + mm \cdot 60 + ss\]

Для кожної секунди в добі, порахуємо скільки виборців знаходились на дільниці в цю секунду.

Для цього будемо підтримувати масив $cnt'_i$. Для кожного виборця знайдемо секунду в яку він прийшов на дільницю $from$ та секунду в яку він покинув дільницю $to$. Збільшимо $cnt'_{from}$ на одиницю та зменшимо $cnt'_{to}$ на одиницю.

Після опрацювання всіх виборців обчислимо $cnt$: масив префіксних сум масиву $cnt'$. Тобто \[cnt_i = \sum_{j = 0}^{i} cnt'_j\] Тепер $cnt_i$ дорівнює кількості виборців які прийшли на дільницю до моменту часу $i$ включно, та покинули її строго після $i$, тобто кількість виборців які знаходились на дільниці в цю секунду.

Відповідь це кількість секунд між 8:00:00 та 20:00:00 не включно, в які кількість виборців на дільниці рівна нулю.

Складність алгоритму $O(n + t)$, де $t$ - кількість секунд в добі.

Також існує розв’язок за $O(n \cdot \log{n})$.

Код розв’язку C++

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

D. Агітації

Розвернемо рядки $p$ та $r$. Отримані рядки назвемо $p'$ та $r'$ відповідно.

Тепер задача полягає в знаходженні найменшої кількості префіксів рядка $p'$ які в конкатенації дають рядок $r'$.

Для зручності також позначимо довжину рядків $p'$ та $r'$ як $n$ та $m$ відповідно.

Доведемо, що існує оптимальна відповідь, в якій довжина останнього префіксу максимально можлива. Для цього розглянемо два різних суфікси $r'[i..m - 1]$, та $r'[j..m - 1]$, де $i < j$, причому обидва суфікси є префіксами рядка $p'$. Нехай оптимальна відповідь містить префікс $r'[j..m - 1]$. Замінимо в цій відповіді останній префікс на $r'[i..m - 1]$, кількість елементів в відповіді при цьому не зміниться. Тепер існує відрізок $r'[i..j - 1]$, кожен символ в якому покритий двома префіксами $p'$. Всі старі префікси які повністю містяться в відрізку $[i..j - 1]$ тепер можна викинути, кількість елементів в відповіді від цього може тільки зменшитись. А єдиний префікс $r'[l..k]$, такий що $l < i \le k$, тобто такий, що його частина покривається префіксом $r'[i..m - 1]$, може бути замінений на префікс $r'[l..i - 1]$, тому що якщо $r'[l..k]$ — префікс $p'$, то $r'[l..i - 1]$ — також префікс $p'$. В результаті такої заміни кожен елемент з $r'$ буде покритий рівно одним префіксом, і кількість префіксів збільшитись не може. А отже в результаті такого процесу можна будь-яку відповідь перетворити до вигляду коли останній префікс має максимально можливу довжину, в тому числі і оптимальну відповідь. Зафіксувавши останній префікс, можна аналогічними міркуваннями почати збільшувати довжину передостаннього і т.д.

В результаті одна з оптимальних відповідей може бути побудована таким жадібним алгоритмом: знаходимо найбільший префікс рядка $p'$ який співпадає з суфіксом рядка $r'$, тоді видаляємо цей суфікс, і збільшуємо відповідь на 1. Повторюємо цей процес поки рядок $r'$ не стане порожнім.

Для того щоб навчитися швидко знаходити найбільший суфікс рядка $r'$, який співпадає з префіксом рядка $p'$ можна використовувати префіксну функцію. А саме: обчислимо префіксну функцію $\pi$ від рядка $p' + \$ + r'$. Тоді довжина найдовшого префікса $p'$ який співпадає з суфіксом $r'$ буде значенням $\pi$ на позиції $n + m$. Оптимальні довжини всіх наступних префіксів можна знайти в тому ж масиві по черзі віднімаючи від позиції довжину останнього префіксу.

Складність алгоритму $O(n + m)$.

Код розв’язку C++

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

A. Капсула для вакцини

Потрібно знайти найменший з вимірів ящика. Це і буде діаметром максимальної сфери, яка поміститься.

Складність розв’язку — $O(1)$.

Код розв’язку C++

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

B. Народна вакцина

Нам задано перший та тринадцятий члени арифметичної прогресії. З означення арифметичної прогресії, ми знаємо, що $A_k = A_1 + (k-1) \cdot d$, де $A_i$ - $i$-тий член арифметичної прогресії, а $d$ її різниця. З цієї формули випливає, що $d = \frac{A_k - A_1}{k-1}$, що для $k=13$ дає $d = \frac{A_{13} - A_1}{12}$.

Зрозуміло, що усі члени арифметичної прогресії є цілими лише у випадку, якщо перший член і різниця цієї прогресії є цілими. Умова гарантує, що перший член є цілим, а тому нам треба перевірити лише різницю. Тобто, перевірити чи $B-A$ ділиться без остачі на 12.

Якщо різниця є цілою (зауважте, що вона може бути й від’ємною, це ні на що не впливає), то нам потрібно знайти суму перших тринадцяти членів цієї прогресії. Загальновідома формула для суми перших $k$ членів — $S_k = \frac{(A_1 + A_k) \cdot k}{2}$, а тому відповідь на задачу це $\frac{(A+B) \cdot 13}{2}$.

Складність розв’язку — $O(1)$.

Код розв’язку C++

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

C. Аморальні експерименти

Усіх людей за столом можна розділити на проміжки (тут проміжком називається множина людей, що сидять підряд), такі що кожен проміжок є або повністю зараженим, або повністю не зараженим. Зауважте, що оскільки стіл круглий, то перший учасник є сусідом останнього. Наприклад, стіл з восьми учасників {0 1 1 0 0 0 1 0} ділиться на 4 проміжки:

незаражений проміжок довжини 2, що включає першого та останнього учасника,
заражений проміжок довжини 2, що включає другого та третього учасника,
незаражений проміжок довжини 3, що включає учасників з четвертого по шостого,
заражений проміжок довжини один, що включає лише сьомого учасника.

Зрозуміло, що кожен незаражений проміжок ставатиме коротшим на два кожної хвилини, оскільки два крайні учасники заразяться від сусідніх заражених. Тобто, проміжок довжини $k$ повністю заразиться за $\lceil \frac{k}{2} \rceil$ хвилин. Усі учасники за столом захворіють, як тільки повністю заразиться найдовший з незаражених проміжків.

Отже, все що потрібно зробити — це знайти довжину найдовшого незараженого проміжку за круглим столом. Один зі способів це зробити такий: повторимо початковий масив двічі і просто знайдемо довжину найдовшого незараженого проміжку так, якби учасники сиділи не за круглим столом, а просто в рядок.

Складність розв’язку — $O(n)$.

Код розв’язку C++

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

D. Закордонна подорож

Припустимо, що в нас є необмежений запас вакцини першого типу, але лише одна вакцина другого типу. Якщо ми всім дамо вакцину першого типу, то сумарна користь становитиме $A_1 + A_2 + ... + A_n$. Якщо $i$-тій людині ми дамо вакцину другого типу, замість першого, то ця користь зміниться на $B_i - A_i$. Отже, вакцину другого типу є зміст давати лише учаснику в якого $B_i - A_i$ максимальне і лише в випадку, коли $B_i - A_i$ додатне для нього.

Аналогічно, якщо в нас є лише дві дози другої вакцини, то їх може бути зміст давати лише двом учасниками з найбільшими значеннями $B_i - A_i$.

Узагальнюючи ці міркування, отримуємо повний розв’язок. Впорядкуємо всіх учасників за незростанням $B_i - A_i$. Другу вакцину отримає деяка група людей, що стоїть на початку в цьому посортованому списку. Треба лише визначити скільком людям на початку списку вигідно дати другу вакцину. Очевидно, що ідеально було б дати вакцину другого типу усім в кого значення $B_i - A_i$ додатне, а решті дати вакцину першого типу. Але у цьому випадку нам може не вистачити вакцин одного з типів. А тому треба також врахувати, що другу вакцину ми маємо дати не менше ніж $n - x$ учасникам та не більше ніж $y$ учасникам.

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

Код розв’язку C++

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

E. Весела ізоляція

Якщо сума всіх елементів масиву парна, то Зеник виграє перших ходом. В іншому випадку, якщо Зеник залишить суму елементів непарною, Марічка виграє своїм наступним ходом. Щоб цього уникнути, Зенику потрібно своїм ходом обов’язково змінити парність суми масиву. Єдиний спосіб це зробити — взяти деякий відрізок парної довжини з непарною сумою, та замінити всі елементи в ньому на одинички. Тоді сума всіх елементів масиву зміниться з непарної на парну. Це єдиний спосіб Зенику уникнути негайного програшу після наступного ходу Марічки.

Зауважимо, що роблячи такий хід, Зеник збільшує кількість одиничок в масиві. Якщо Марічка буде дотримуватимуться такої ж стратегії, то кількість одиничок буде збільшуватися після кожного ходу, а тому, рано чи пізно, всі елементи стануть одиничками, і переможе Марічка. Тобто, незалежно від своїх ходів, Зеник не має жодного шансу на перемогу.

Отже, переможець гри однозначно визначається парністю суми всіх елементів масиву.

Складність розв’язку — $O(n)$.

Код розв’язку C++

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

F. ДНК реп’яховiрусу

Нехай $n$ — довжина рядка $T$, а $m$ — довжина рядка $S$.

Якщо $n < m$, то відповідь 0, адже ми не можемо знайти жодного підрядка потрібної довжини у $T$.

Подивимося який вклад у загальну відповідь внесе перший символ рядка $S$: він додасть до відповіді 1 за кожен такий же символ рядка $T$, де може починатися підрядок довжини $m$ (тобто символи від 1 до $n-m+1$). Аналогічно, другий символ рядка $S$ додасть до відповіді 2 за кожен такий же символ $S$ з проміжку від 2 до $n-m+2$.

Узагальнюючи, отримуємо, що вклад $i$-го символу рядка $S$ у відповідь становитиме $i \cdot count_T(S_i, i, n-m+i)$, де $count_T(x, l, r)$ — це кількість символів $x$ у рядку $T$ на проміжку від $l$ до $r$.

Отож, якщо ми навчимося швидко шукати $count_T(x, l, r)$, то задача розв’язана. Зауважимо, що у рядка, який складається з малих літер латинської абетки може бути щонайбільше 26 різних символів.

Заведемо двовимірний масив розміром $26 \times n$. Нехай $A_{i,j} = 1$, якщо $j$-й символ рядка $T$ є $i$-тим символом алфавіту. Тепер, щоб знайти $count_T(x, l, r)$ нам потрібно знайти суму на відповідному відрізку одновимірного масиву $A_{i}$. Для цього скористаємося відомим методом, який називається часткові суми.

Нехай $B_{i,j} = A_{i,1} + A_{i,2} + ... + A_{i,j} = B_{i, j-1} + A_{i, j}$. Тепер, зрозуміло, що $count_T(x, l, r) = A_{i,l} + A_{i,l+1} + ... + A_{i,r} = B_{x, r} - B_{x, l-1}$.

Отже, обчисливши один раз масив $B$ зі складністю $O(26 \cdot n)$, ми зможемо знаходити $count_T(x, l, r)$ за $O(1)$. Загальна складність розв’язку — $O(26 \cdot n)$.

Код розв’язку C++

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

F. Розробка вакцини

Яка довжина найкоротшого шляху, що починається в корені дерева проходить через усі листки дерева, а тоді повертається у корінь? Легко бачити, що такий шлях проходить по кожному ребру рівно 2 рази, а тому його довжина — $2n - 2$, де $n$ — кількість вершин у дереві.

Як змінюється ця довжина якщо нам не потрібно повертатися в корінь після відвідування останнього листка? Нехай $D_v$ — відстань від кореня до вершини $v$ (ми також називатимемо цю величину глибиною вершини $v$). Зрозуміло, що закінчивши у листку $x$, ми економимо рівно $D_x$ ребер. Отже, вигідно закінчити наш маршрут у вершині, для якої $D_v$ максимальне.

Таким чином, щоб відповісти на запит другого типу нам потрібно знати кількість вершин у піддереві, а також глибину найглибшого листка. Якби не було запитів першого типу, то було б достатньо обчислити ці значення для усіх вершин за допомогою пошуку в глибину. Як же бути з запитами першого типу? Від задачі з додаванням вершин перейдемо до задачі з "увімкненням" вершин. Розглянемо дерево, що вийде після виконання усіх запитів першого типу (ми називатимемо його фінальним деревом). Тепер вважатимемо, що кожна вершина в цьому дереві може бути або увімкненою, або ні. Коли відбувається запит першого типу, то ми вмикаємо відповідну вершину. Для запиту другого типу нам потрібно знайти кількість увімкнених вершин у піддереві та максимальну глибину серед увімкнених вершин у піддереві.

Побудуємо Ейлеровий обхід фінального дерева: випишемо усі вершини дерева в порядку обходу в глибину. Кожному піддереву відповідає деякий неперервний відрізок в цьому обході. Це дозволяє перетворити запити на піддереві у запити на відрізку. Отож, тепер нам потрібна структура даних, що ефективно виконує такі операції:

змінити значення елемента (щоб увімкнути вершину)
знайти суму на відрізку (щоб знайти кількість вершин у піддереві)
знайти максимальний елемент на відрізку (щоб знайти найглибшого листка)

Одна з таких структур — дерево відрізків. Вона може виконувати кожен з цих запитів з логарифмічною складністю.

Загальна складність — $O(n + q \log(n))$.

Код розв’язку C++

A.Цікава гра

Під час кожного ходу рівно одна біла клітинка зафарбовується в чорний колір. Отже, загальна кількість ходів рівна кількості білих клітинок на дошці. На дошці є $n \cdot m$ білих клітинок. Якщо ця кількість парна, то Дракон зробить останній хід і переможе в грі. Інакше переможе Бісеня.

Код розв’язку C++

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

B.Зуби

Пройдемось по масиву зліва направо і будемо підтримувати $cur$ — кількість послідовних елементів більших або рівних за $k$, закінчуючи в цій позиції включно. Якщо черговий елемент $x \ge k$, то $cur$ збільшується на один, інакше $cur$ стає рівним нулю. Відповідь буде максимум зі значень $cur$ в кожній позиції масиву.

Код розв’язку C++

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

C. Вогняне дихання

Порахуємо $distances_i$ — відстань від хатинки сеньйора до $i$-тої точки, де дракон дмухав вогнем. Після цього впорядкуєм масив $distances$. Відповідь рівна значенню $distances_k$ у відсортованому масиві.

В C++ замість сортування можна використати стандартну функцію std::nth_element, яка дозволяє за лінійний час знайти, яке значення було б на певній позиції, якби масив впорядкували.

Код розв’язку C++

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

D. Дівчата

Одну з оптимальних послідовностей операцій можна побудувати наступним чином.

Якщо у матриці кожен зі стовпців має вигляд RR або BB, то кожен стовпець BB може бути замінений на RR за одну операцію другого типу. В такому випадку відповідь буде рівна кількості стовпців BB.

В іншому випадку в матриці існують стовпці RB або BR. В такому випадку жадібно розіб’ємо матрицю на відрізки по стовпцях так, щоб в кожному відрізку не було одночасно стовпців RB та BR. Нехай всього таких відрізків є $x$. Тоді за $\lfloor \frac{x} {2} \rfloor$ операцій можна замінити всі RB (або BR, в залежності від того яких відрізків менше) на RR застосувавши операцію третього типу до відповідного відрізка. Після чого за ще одну операцію можна замінити всі BR (або RB, в залежності від того, які стовпці залишились) на RR застосувавши операцію третього типу до всієї матриці. Після цього ще можуть залишитись стовпці вигляду BB, кожен з яких можна замінитина RR послідовно застосовуючи операцію другого типу до пари сусідніх стовпців RR та BB.

Доведення оптимальності залишаємо читачу.

Час роботи жадібного алгоритму $O(n)$.

Також існує розв’язок за допомогою динамічного програмування за $O(n^3)$.

Код розв’язку C++

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

Код розв’язку C++ методом динамічного програмування за $O(n^3)$

A.Цікаве листування

Щоб розшифрувати повідомлення потрібно зробити зворотний процес до того, який зробив Зеник для шифрування. Розглянемо один із простих в реалізації способів.

Розділимо зашифроване повідомлення на $k$ рядків. Отримали матрицю $k \times k$. Всього в матриці є $2 \cdot k - 1$ діагональні лінії, $x$-а з яких складається з елементів матриці $A_{i,j}$, таких що $x = i + j$ та $0 \le i, j < k$. Переберемо спочатку номер лінії $x$ (від 0 до $2 \cdot k - 2$), а потім $i$ (від 0 до $k - 1$), знаючи $x$ та $i$ можна легко визначити $j = x - i$. Якщо отримане $j$ знаходиться в межах від 0 до $k - 1$, то відповідний елемент матриці потрібно додати до відповіді.

Код розв’язку C++

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

B. Конкурс талантів

Переберемо верхній лівий одиничний квадрат та довжину сторони великого квадрата. Для кожного такого великого квадрата порахуємо кількість одиниць в ньому. Відповідь рівна максимуму з довжин великого квадрата серед усіх таких квадратів в яких кількість одиниць не перевищує $k$.

Час роботи алгоритму $O(n^5)$ і цього достатньо для обмежень в задачі.

Також існують розв’язки за $O(n^3)$ та $O(n^2 \cdot \log{n})$

Код розв’язку C++

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

C. Нечесна конкуренція

Побудуємо граф, вершинами якого будуть учні. Дві вершини з’єднаємо ребром, якщо відповідні учні дружать між собою.

Тепер можна сформулювати задачу наступним чином: Петрик (якому відповідає вершина з номером 1) може намовити голосувати за Христину всіх учнів, які знаходяться в його компоненті зв’язності. Скількома способами Зеник може видалити ребро з графу так, щоб в компоненті зв’язності Петрика стало менше ніж $n$ вершин?

Нескладно побачити, що задача полягає в знаходженні кількості мостів у графі. Тобто таких ребер, при видаленні яких граф розпадеться на дві компоненти зв’язності.

Розглянемо простий спосіб знаходження мостів в графі. Переберемо ребро, яке видалить Зеник. Тепер видалимо його з графу, і запустимо обхід в глибину з будь-якої вершини. Якщо в процесі цього обходу будуть відвідані не всі $n$ вершин, то це означає що видалене ребро є мостом. В такому випадку додамо один до відповіді. Важливо не забути повернути ребро назад перед розглядом наступного ребра.

Час роботи такого алгоритму $O(m \cdot (n + m))$, чого достатньо для даних обмежень.

Також існує спосіб знаходити мости в графі за $(n + m)$.

Код розв’язку C++

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

D. Підготовка до конкурсу

Застосуємо метод динамічного програмування. Нехай $dp[pos][nonzero][less][mask]$ дорівнює кількості способів побудувати префікс числа яке не перевищує $n$ довжини pos, використовуючи цифри які входять в бітову маску $mask$.

Параметр $less$ рівний 0, якщо префікс повністю збігається з відповідним префіксом n, або 1, якщо префікс лексикографічно менший. Параметр $nonzero$ рівний 1, якщо на префіксі вже є ненульова цифра, або 0, якщо таких немає.

Ініціалізація проста — $dp[0][0][0][0] = 1$, всі інші стани рівні нулю.

Для зручності позначимо як $s[i]$ $i$-тий символ в десятковому записі числа $n$ (нумеруємо з 0, зліва направо).

Розглянемо переходи зі стану $dp[pos][nonzero][less][mask]$. Якщо $less$ рівний нулю, то на цю позицію можна поставити лише цифру яка не перевищує $s[pos]$. Інакше, оскільки наше число вже менше за $n$, то на цю позицію можна поставити будь-яку цифру від 0 до 9. Переберемо цифру яку будемо ставити на цей розряд. Нехай ми хочемо поставити цифру $d$. Знайдемо нову маску з цифр $nmask$. Вона дорівнює старій масці із включеним бітом для цифри $d$. Оскільки ми не хочемо будувати числа з ведучими нулями, то якщо наш префікс складається лише з нулів ($nonzero$ дорівнює 1) біт для цифри 0 включати в нову маску не будемо. Нове значення параметру $less$ обчислити просто: якщо $less$ вже був 1, то й залишиться 1. Інакше $less$ стане рівне 1 тільки якщо $d < s[pos]$. Параметр $nonzero$ буде рівний 1, якщо він вже рівний 1, або ж якщо $d \neq 0$. Параметр $pos$ при збільшенні довжини префіксу на 1 стане рівним $pos + 1$.

Після цього для зручності порахуємо $cnt[mask]$ - кількість чисел, які не перевищують $n$, та складаються з цифр із маски $mask$. $cnt[mask]$ дорівнює сумі $dp[|s|][nonzero][less][mask]$ по всіх можливих значенням параметрів $nonzero$ та $less$ (0 або 1).

Тепер розглянемо всі пари масок $a$ та $b$. Якщо ці маски мають спільний біт, то відповідні числа мають спільні цифри. В такому випадку, до відповіді потрібно додати добуток $cnt[a] \cdot cnt[b]$, тому що існує саме стільки пар чисел з відповідними наборами цифр.

В процесі роботи алгоритму буде обчислено не більше ніж $11 \cdot 2 \cdot 2 \cdot 1024 = 45056$ станів динамічного програмування, з кожного з них буде не більше 10 переходів, що в сумі дасть не більше ніж 450560 переходів з невеликою константою. Після цього потрібно розглянути $1024^2$ пар масок. Загальна кількість операцій не перевищує кількох мільйонів, що з легкістю вкладається в обмеженя задачі.

Код розв’язку C++

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

A.Пароль для Марічки

Знайдемо найменше число $x = 10^n$ таке, що $x \ge l$. Якщо $x \le r$ то відповідь $x$. Інакше числа $l$ та $r$ складаються з однакової кількості цифр. В такому випадку лексикографічне порівняння не відрізняється від звичайного, а отже лексикографічно найменшим числом з відрізка від $l$ до $r$ буде число $l$.

Код розв’язку C++

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

B.Зеник і НСД

Будь-яке парне число оптимально подати у вигляді послідовності з $\frac{s} {2}$ двійок. Непарні числа менші за 9 можна подати тільки одним числом $s$. Число 9 найоптимальніше подати у вигляді 3, 3, 3. Непарні числа більші за 9 вигідно подати у вигляді послідовності 3, 6, 2, 2, 2…, тобто кількість чисел буде рівна $2 + \frac{s - 9} {2}$.

Код розв’язку C++

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

C. Найкраще привітання

Позначимо вхідний рядок змінною $s$. Нехай $t$ — лексикографічно мінімальний рядок який можна отримати перестановкою букв $s$, тобто $t$ — рядок $s$ у якому елементи впорядковані за неспаданням.

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

Подивимося, як знаходити найменший рядок з урахуванням обмеження на кількість позицій котрі можна вирізати. Будемо йти зліва направо. Якщо $s_0 = t_0$, то перший символ покращити не можливо. Інакше, якщо $s_0 \neq t_0$, то можна знайти в рядку $s$ букву $t_0$, вирізати її разом з $s_0$ та поміняти їх місцями. Таким чином, вирізавши два символи ми дістали кращий рядок. Схожі міркування продовжеємо з наступними буквами по порядку.

В загальному, розглянемо перші $x$ букв. Порахуємо, скільки букв треба вирізати, для того щоб префікс довжини $x$ рядка $s$ співпадав з префіксом рядка $t$. Усі позиції будуть одного з двох типів, або $s_i = t_i$, або $s_i \neq t_i$. В першому випадку нічого вирізати не треба. Проте, всі позиції у яких виконується друга умова треба вирізати, тому що на цих позиціях треба поставити інші символи. Виріжемо всі такі позиції. Нехай їх є $m$ штук. Тепер, для кожної з них треба знайти в рядку $s$ букву $t_i$, вирізати її, і поставити на місце $s_i$, тобто всього треба вирізати $m \cdot 2$ символів. Проте, це можна зробити краще. Якщодля якоїсь позиції $i$ існує $j < x$, таке що $s_j \neq t_j$ і $t_i = s_j$, то на місце $i$ можемо поставити букву $s_j$, котру ми і так будемо вирізати. Цим ми економимо одне вирізання.

Загалом, для того щоб порахувати скільки букв треба вирізати для префікса довжини $x$, для кожного символа $c$ порахуємо дві величини: $A_c$ — кількість таких $i < x$, що $s_i \neq t_i$ і $s_i = c$, а також $B_c$ — кількість таких $i < x$, що $s_i \neq t_i$ і $t_i = c$. $A_c$ — це кількість символів $c$, які ми вирізали, а $B_c$ — кількість позицій, на які символ $c$ треба поставити. Зрозуміло, що $min(A_c, B_c)$ символів можемо зразу поставити на своє місце, а $B_c - min(A_c, B_c)$ треба ще вирізати додатково. Таким чином, загальна кількість символів буде $m + \sum{B_c - min(A_c, B_c)}$.

Для досягнення лексикографічної мінімальності треба обрати найбільше таке $x$, що необхідна кількість вирізаних символів не перевишує $k$. Це можна зробити двійковим пошуком.

Щоб знайти відповідь до задачі, знайдемо оптимальне $x$. Перші $x$ символів відповіді співпадатимуть з рядком $t$. Далі треба знайти які символи треба ще додатково вирізати, і замінити їх на надлишок символів, котрі ми вирізали з префікса. З міркувань лексикографічної мінімальності треба вирізати їх якомога правіше, а вставляти в лексикографічному порядку.

Код розв’язку C++

D. Готуй адвокатів

Коректний список доріг у країні має утворювати повне двійкове дерево з висотою $h$ - 1, а також 3 додаткові ребра, які потрібно знайти. Оскільки кожне з трьох додаткових ребер утворює цикл в дереві, то кандидатами на відповідь можуть бути лише ті ребра, які не є мостами в графі. Знайдемо всі такі ребра. Так як загальна кількість ребер в графі не перевищує 1025, то можна шукати всі мости за $O(n^2)$ (де $n$ - кількість вершин в графі), просто видаляючи всі ребра по одному і перевіряючи зв’язність. Отримали множину кандидатів на відповідь.

Оскільки діаметр повного двійкового дерева в не перевищує $2 \cdot h$, то при додаванні до дерева одного ребра можна отримати цикл довжиною не більше $2 \cdot h$. А значить, при додаванні трьох ребер, загальна кількість ребер в циклах не перевищуватиме $6 \cdot h$. В обмеженнях задачі $6 \cdot h \le 60$. Отже якщо множина кандитатів містить більше як 60 ребер, то це означає що набір доріг точно не є коректним і відповідь -1. Інакше переберемо всі трійки різних ребер з множини кандидатів в лексикографічному порядку, після чого перевіримо чи після видалення їх з графу в результаті залишається повне двійкове дерево.

Для перевірки чи граф є повним двійковим деревом можна скористатись наступним критерієм. В графі має бути рівно одна вершина степені 2 — корінь, і рівно $2^{h - 1}$ вершини степені 1 — листки. Всі інші проміжні вершини мають мати степінь 3. Залишилось перевірити чи граф зв’язний і чи висота дерева рівна $h - 1$. Для цього можна запустити обхід в глибину починаючи з кореня та підтримувати максимальну глибину серед усіх відвіданих вершин а також їхню кількість.

Отримали алгоритм який працює за $O(n^2 + n \cdot h^3)$.

Код розв’язку C++

A. Зеник і задачі

Очевидно, що перший алгоритм потрібно завжди реалізувати з нуля. Для всіх інших циклом пройдемо по них (від другого до останнього) та перевіримо, чи відрізняється поточний алгоритм від попереднього. Якщо відрізняється, додамо до відповіді 1.

Код розв’язку C++

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

B. Коржі

Серед коржів з однаковим радіусом необхідно вибрати той, що має найбільший об’єм. Коржі з різними радіусами завжди можна поставити так, аби корж зверху мав менший радіус, ніж корж знизу. Отже, потрібно просто просумувати максимальні об’єми по всіх унікальних радіусах.

Код розв’язку C++

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

C. Не можу пригадати пароль!

Один зі способів згенерувати паролі — це розглянути числа від 1 до $n$ в системі числення з основою $k$. Цифра 0 відповідатиме букві a, 1 — b, і т. д.

Записати число $x$ в системі числення з основою $k$ доволі просто — для цього необхідно $m$ разів виконувати такий процес: візьмемо остачу від ділення $x$ на $k$ та цілочисельно поділимо $x$ на $k$. Остачі від ділення на кожному кроці утворюють число в системі числення з основою $k$.

Код розв’язку C++

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

D. Перестановка

\[\sum_{i=1}^n |p_i - i| \equiv \sum_{i=1}^n p_i + \sum_{i=1}^n i \equiv \frac{n(n+1)}{2}+\frac{n(n+1)}{2} \equiv n(n+1) \equiv 0 \mod 2\]

Отже, якщо $k$ непарне, то відповідь NO.

Якщо $k \le 2 \cdot (n - 1)$, тоді ми можемо побудувати таку перестановку: \[\left(\underline{\frac{k}{2}+1}, 2, 3, \ldots, \frac{k}{2}-1, \frac{k}{2}, \underline{1}, \frac{k}{2}+2, \frac{k}{2}+3, \ldots, n - 1, n\right)\]

Якщо $k > 2 \cdot (n-1)$, тоді зробимо $p_1 = n$ і $p_n = 1$. $|p_1-1|+|p_n-n|=2 \cdot (n-1)$. Зменшимо $k$ на $2 \cdot (n - 1)$ і розв’яжемо меншу задачу на підпослідовності $(2, 3, \ldots, n - 1)$, використовуючи аналогічні міркування. Якщо на якомусь кроці ми використали всі елементи перестановки, але $k$ все ще більше за 0, значить розв’язку не існує і відповідь — NO.

Приклад для $n=11$, $k=44$.

$(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11) \xrightarrow{\text{+20}} (\underline{11}, 2, 3, 4, 5, 6, 7, 8, 9, 10, \underline{1}) \xrightarrow{\text{+16}} (11, \underline{10}, 3, 4, 5, 6, 7, 8, 9, \underline{2}, 1) \xrightarrow{\text{+8}} (11, 10, \underline{7}, 4, 5, 6, \underline{3}, 8, 9, 2, 1)$.

Код розв’язку C++

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

E. Прямокутна ковзанка

Спробуємо перевірити, чи існує квадрат розміру $k \times k$ який має усі елементи менші за $x$.

Утворимо новий масив $a_{i j} = 0$, якщо $d_{i j} \le x$ або $a_{i j} = 1$ інакше. Тоді порахувавши префіксні суми, ми можемо знайти суму в одному квадраті $k \times k$ за $O(1)$.

Переберемо всі квадрати, і якщо хоча б в одному з них сума буде рівна $0$ — це означатиме, що квадрат не містить елементів більших за $x$.

Тепер ми можемо скористатися методом двійкового пошуку для того, аби знайти мінімальне значення $x$, для якого існує квадрат $k \times k$, що містить усі елементи не більші за $x$. Це значення й буде відповіддю на задачу.

Код розв’язку C++

Код розв’язку Python (набирає 10 балів)

F. Гра з многокутником

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

Якщо розглянути трикутник, який складається не з трьох послідовних вершин, зафіксувати дві з них, і сунути третю в один з двох напрямків по вершинах многокутника, довжина висоти буде зменшуватись, а отже площа трикутника також буде зменшуватися. Такий процес можна продовжувати, поки вершини трикутника не будуть послідовними вершинами многокутника. На рисунку площі трикутників $ABD$ та $ABE$ менші за площу трикутника $ABC$, бо відстані від точок $D$ та $E$ до прямої $AB$ менші за відстань від точки $C$ до цієї прямої.

Тепер подивимось на те, як буде грати Зеник. Оскільки він хоче мінімізувати площу трикутника, то на своєму ході він просто обере найменший трикутник з трьох послідовних вершин многокутника й розріже многокутник уздовж відповідної діагоналі. На цьому гра завершиться.

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

Відповідь на задачу — найбільша площа трикутника з трьох послідовних вершин многокутника.

Код розв’язку C++

G. Розвезення води

Розглянемо дві сусідні станції $j$ та $j+1$. Між ними розташовані будинки з індексами від $l$ до $r$.

Сформулюємо та доведемо таке твердження. Для деякого оптимального розв’язку існує такий індекс $s$, $l \le s \le r$, що потреби $i$-ого будинку будуть повністю забезпечені водою з $j$-ої станції при $l \le i < s$, повністю покриті водою з $(j+1)$-ої станції при $s < i \le r$, а потреби $s$-ого будинку — частково з $j$-ої, частково з $(j+1)$-ої станцій (можливо, повністю з однієї станції).

Доведення. Припустимо, що до $i$-го будинку, де $l \le i \le r$ привезли воду з $t$-ї станції, $t<j$. Це не вигідно, бо цю воду можна було привезти з $j$-ї станції, тоді сумарна відстань буде меншою. Аналогічно невигідно везти воду з $t$-ї станції, якщо $t>j+1$.

Отже, потреби всіх будинків між станціями $j$ та $j+1$ вигідно покрити водою із цих станцій.

Нехай $i_1$ — найправіший будинок, до якого везли воду з $j$-ї станції, а $i_2$ — найлівіший, до якого везли з $(j+1)$-ї.

Припустимо, що $i_2<i_1$. Нехай до $i_1$-го будинку з $j$-ї станції привезли $c_1$ літрів води, а до $i_2$-го з $(j+1)$-ї — $c_2$ літрів. Позначимо $d=\min\{c_1, c_2\}, c_1’=c_1-d, c_2’=c_2-d$.

Якщо до $i_1$-го будинку з $j$-ї станції привезуть $c_1’$ літрів води, до $i_2$-го з $(j+1)$-ї станції — $c_2’$ літрів, а недостачу $d$ літрів для $i_1$-го та $i_2$-го будинків будуть покривати відповідно $(j+1)$-а та $j$-а станції, то сумарна відстань зменшиться, позаяк $c_1’$ або $c_2’$ дорівнює нулю.

Отже, $i_1 \le i_2$.

Потреби будинків з номерами меншими за $i_1$ буде покривати $j$-а станція, більшими за $i_1$ — $(j+1)$-а станція. Якщо $i_1=i_2$, то потреби $i_1$-го будинку будуть покривати обидві станції. Тому можна взяти $s=i_1$.

Отже, твердження доведено.

Звідси випливає, що проміжки між сусідніми станціями можна розв’язувати незалежно один від одного. Задача розбивається на підзадачі з двома станціями $j$ та $j+1$ та будинками між ними. Навчимося розв’язувати таку підзадачу.

Розв’язок за $O(\sum_{i} a_i)$.

Скористаємося динамічним програмуванням.

Нехай $dp_1[x]$ — мінімальна відстань, яку має проїхати автомобіль з лівої станції, щоб відвезти будинкам $x$ літрів води. $x$ однозначно визначає, яким будинкам скільки води привезе автомобіль. Нехай $i$ — найправіший будинок, якому лівий автомобіль привезе воду. Тоді $dp_1[x] = dp_1[\max\{0, x - k\}]+2(h_i-s_j)$.

Таку саму динаміку $dp_2$ можна порахувати для правої станції. Відповіддю на підзадачу буде $\min_x dp_1[x]+dp_2[t-x]$, де $t=\sum_{i} a_i$ — сума потреб будинків.

Код розв’язку C++

Розв’язок за $O(n^2 \log n)$.

Розглянемо числову пряму, на якій число $x$ відповідає $x$ літрам води. $l$-му будинкові відповідає півінтервал $\left(0, a_l \right]$, $(l+1)$-му — $\left(a_l, a_l+a_{l+1} \right]$, $(l+2)$-му — $\left(a_l+a_{l+1}, a_l+a_{l+1}+a_{l+2} \right]$ і т.д. Позначимо кінець півінтервалу, що відповідає $i$-ому будинку $e_i$. Також у кожного будинку є число $f_i=2(h_i-s_j)$ — відстань, яку має проїхати автомобіль від $j$-ої станції до будинку й назад. Динаміку $dp_1$ з попереднього розв’язку можна уявити на цій прямій: остання поїздка автомобіля — це стрибок з точки $x-k$ в точку $x$, за цей стрибок платимо $f_i$, де $i$ — номер будинку, чиєму півінтервалу належить точка $x$. Процес розвезення води лівим автомобілем можна представити послідовністю точок $w, w + k, w + 2 \cdot k, \dots, w + p \cdot k$ — за першу поїздку відвозимо $w \le k$ літрів, за кожну наступну — $k$ літрів.

Якщо $w<k$ та жодна з точок $w+p \cdot k$ не є кінцем півінтервалу якогось будинку, то можемо кожну точку в послідовності посунути вправо на одиницю, при цьому сумарна відстань не збільшиться (кожна точка залишиться в тому півінтервалі, де вона була), а відвезена кількість літрів (остання точка в послідовності) збільшиться на одиницю. Тому варто розглядати тільки такі $w$, що $w=k$ або такі, що $w+p \cdot k=e_i$ для деяких $p$, $i$, тобто $w \equiv e_i \mod k$ — різних кандидатів на $w$ буде $O(n)$.

Наступне спостереження: якщо лівий автомобіль привіз повну цистерну води до $i$-ого будинку, то він буде продовжувати возити туди повні цистерни, поки може.

Для кожного $w$ маємо таких кандидатів на межу поділу між лівим та правим автомобілями.

Повністю покриваємо потреби будинків до $(i-1)$-ого. Воду, що залишилася, веземо до $i$-ого будинку. Останньою точкою буде такий мінімальний $x$, що $e_{i-1} < x \le e_i$, $x \equiv w \mod k$. Зауважте, що такої точки може не існувати. Назвемо такого кандидата кандидатом типу А.
Повністю покриваємо потреби будинків до $(i-1)$-ого. Воду, що залишилася, веземо до $i$-ого будинку. Возимо повні цистерни до $i$-ого будинку, поки вони туди поміщаються. Останньою точкою буде такий максимальний $x$, що $e_{i-1}+k < x \le e_i$, $x \equiv w \mod k$. Такої точки може не існувати. Назвемо такого кандидата кандидатом типу Б.

Для кожного $w$ при переході між сусідніми кандидатами легко перераховувати відповідь. Якщо кандидат $y$ потрапляє в півінтервал $i$-ого будинку, а попередній кандидат був $x$, то до відповіді додасться $\frac{y-x}{k}f_i$ (число $\frac{y-x}{k}$ ціле).

Для лівого та правого автомобілів порахуємо відповіді для всіх кандидатів.

Щоб знайти відповідь на задачу, треба для кожного кандидата для лівого автомобіля $x$ знайти такого найменшого кандидата $y$ для правого автомобіля, що $x+y \ge t$, де $t=\sum_{i} a_i$ — сума потреб будинків.

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

Складність сортування буде $O(n^2 \log n)$.

Код розв’язку C++

Розв’язок за $O(n^2)$.

Посортуємо всіх кандидатів на $w$. Зауважимо, що в кожному півінтервалі буде не більше як два кандидати з однаковою остачею за модулем $k$ (не більше як один типу А та не більше як один типу Б з такою остачею). Хочемо посортувати кандидатів в $i$-ому півінтервалі за $O(n)$. Спершу знайдемо мінімального кандидата типу А в цьому півінтервалі. Нехай його остача за модулем $k$ дорівнює $z$. Додамо до посортованого списку кандидатів типу А для всіх остач $w$ від $z$ до $k-1$, потім — від 0 до $z-1$. Для цього пройдемося по списку кандидатів на $w$. У такий спосіб ми посортували кандидатів типу А. Так само зробимо з кандидатами типу Б. Отже, посортували всіх кандидатів.

Код розв’язку C++

A. Розфарбування дерева.

Зауважимо, що ми можемо скористатися бінарним пошуком по відповіді.

Маючи зафіксовану відстань $x$, потрібно визначити чи можна розфарбувати дерево у щонайбільше $k$ кольорів так, щоб максимальна відстань між вершинами одного кольору була не більшою за $x$.

Скористаємося методом динамічного програмування. Вважатимемо, що дерево є підвішеним за довільну вершину. Нехай $C_i$ — мінімальна кількість кольорів, необхідна щоб розфарбувати піддерево вершини $i$. Також, нехай $D_i$ — мінімальна можлива при цьому відстань від вершини $i$ до вершини такого ж кольору.

Припустимо, що ми хочемо знайти $C_a$ та $D_a$ для вершини $a$, при тому що нам вже відомі значення $(C_{b_1}, D_{b_1}), (C_{b_2}, D_{b_2}), \dotsc , (C_{b_l}, D_{b_l})$ для усіх синів вершини $a$. Очевидно, що $C_a \le C_{b_1} + C_{b_2} + \dotsc + C_{b_l} + 1$, адже ми можемо усі піддерева розфарбувати незалежно, а самій вершині $a$ присвоїти новий колір. Проте, необхідна кількість кольорів може бути меншою, адже можливо деякі кольори можна об’єднати. Впорядкуємо синів вершини $а$ за зростанням $D_{b_i}$. Тепер розглянемо деякий префікс цього впорядкованого масиву. Зрозуміло, що якщо ми можемо об’єднати кольори двох останніх синів на цьому префіксі, то можемо приєднати й кольори усіх попередніх синів, адже глибина найглибшої вершини для них є небільшою. Отже, нам потрібно просто знайти найдовший префікс для якого останніх двох синів можна об’єднати. Нехай це префікс довжини $k$, тоді $C_a = \sum C_{b_i} - k + 1, D_a = \max D_{b_i}+1$. Зверніть увагу, що випадок, коли жоден з синів вершини $a$ не може бути одного кольору з вершиною $a$ ($min D_{b_i} + 1 > x$), треба обробити окремо.

Загальна складність — $O(n \log^2 n).$

Код розв’язку C++

B. Зеник і рядки

Навчимося ефективно знаходити значення $f(s, t)$. Розглянемо $k$-й префікс рядка $s$ — $s_{1..k}$. Знайдемо усі входження цього префікса у рядок $t$, нехай $p$ — позиція довільного входження. Зрозуміло, що $|lcp(s, t_{p..|t|})| \ge k$ і що в позиції $p$ будуть розпочинатися входження усіх префіксів $s$ довжиною від 1 до $|lcp(s, t_{p..|t|})|$. А тому значення функції $f(s, t)$ є рівним значенню $\sum_{i = 1}^{|s|} cnt(s_{1..i}, t)$, де $cnt(x, y)$ — кількість входжень рядка $x$ у рядок $y$.

Ефективний спосіб шукати кількість входжень кожного префікса рядка $s$ у рядку $t$ є загальновідомим: побудуємо суфіксний автомат по рядку $t$. Потрібно для кожної вершини автомату знайти розмір множини позицій закінчення входжень, якій відповідає ця вершина. Це робиться динамічним програмуванням по дереву суфіксних посилань автомата. Ми не будемо детально зупинятися на цьому прийомі в межах цього розбору, адже цю інформацію можна знайти в інтернеті.

Нам достатньо побувати суфіксний автомат для рядка $t$ всього один раз і використати його для обчислення $f(s_i, t)$ для усіх рядків з набору. Загальна складність розв’язку є лінійною від суми довжин усіх рядків.

Код розв’язку C++

C. Піраміда

Для початку нам потрібно отримати палку довжини 1. Яку палку для цього є зміст використати? Зрозуміло, що нам є зміст укорочувати для цього найкоротшу палку. Аналогічно, палку довжини 3 є зміст робити з найкоротшої палки, довжини щонайменше 3, яка ще не використана для отримання палки довжини 1. Продовжуючи ці міркування, отримуємо повний розв’язок. Впорядкуємо палки в порядку неспадання довжини. Роблячи один прохід по впорядкованому масиву зліва на право, знайдемо спочатку яку палку ми будемо використовувати, щоб отримати довжину 1, яку щоб 3 і так далі. В якийсь момент ми не зможемо знайти палку, щоб отримати чергову необхідну довжину. Остання довжина, для якої ми успішно знайшли палку і є відповідь на задачу.

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

Код розв’язку C++

D. Гарний масив

Скористаємося методом динамічного програмування. Нехай $D_k$ — відповідь на задачу, якщо в нас є лише перші $k$ чисел. Як, знаючи $D_1, D_2, \dotsc, D_k$, знайти $D_{k+1}$? Переберемо, яке буде останнє невидалене число безпосередньо перед $(k+1)$-шим. Якщо воно є взаємно простим з останнім, то відповідь не зміниться, а в іншому випадку — зросте на одиницю. Тобто, $D_{k+1} = \max_{i=1}^k (D_{i} + [gcd(a_{k+1}, a_i) \neq 1])$.

Складність такого розв’язку — $O(n^2 \log(\max a_i))$ — цього недостатньо.

Ведемо словник $M$, який підтримуватимемо під час обрахунку значень динамічного програмування. Нехай $p$ — просте число, тоді $M_p$ — найбільше з вже обчислених значень $D_i$, таке що $a_i$ ділиться на $p$. Тепер перехід динамічного програмування, можна описати так:

$D_{k+1} = \max(\max_{p\ is\ prime,\ p | a_{k+1}}(M_p + 1), D_k)$.

Зрозуміло, що кількість простих дільників числа $a_{k+1}$ є логарифмічного порядку, а тому для знаходження нового значення динамічного програмування нам потрібно розглянути щонайбільше логарифм значень зі словника $M$. Аналогічно, після знаходження нового значення динамічного програмування, нам потрібно оновити щонайбільше логарифм записів у словнику $M$. Таким чином, якщо вважати що нам відома факторизація усіх чисел, а звернення до елементів словника відбувається з логарифмічною асимптотикою, то сумарна складність становитиме $O(n \log^2 (\max a_i))$, що є прийнятним для обмежень задачі.

Єдине, що залишилося зробити — факторизувати усі вхідні числа. Факторизувати можна за $\sqrt{a_i}$, проте можуть виникнути проблеми з часом роботи алгоритму, тому можна використати таку оптимізацію. Скориставшись решетом Ератосфена знайдемо усі прості числа, менші за $\sqrt{\max a_i}$. Кількість таких простих чисел, що менші за $k$ можна оцінити як $O(\frac{k}{\log k})$. Кожне число вхідних даних будемо ділити на кожне з знайдених простих чисел доки це можливо. Якщо після усіх ділень отримане число не рівне одиниці, то ми знайшли єдиний простий дільник, який є більшим за $\sqrt{\max a_i}$. Таким чином ми знайдемо факторизацію усіх вхідних чисел зі складністю $O(n \frac{\sqrt{\max a_i}}{\log \max a_i})$.

Код розв’язку C++

E. Кількість пар

У задачі просять порахувати кількість пар чисел на проміжку $[l, r]$, що їхнє "побітове і" рівне нулю.

Нехай $C(x, y)$ — кількість пар чисел $(a, b)$, таких що $a \le x,\ b \le y,\ a \mbox{ AND } b = 0$. Згідно з принципом включення-виключення, кількість пар чисел $(a, b)$, що відповідають обмеженням $l \le a \le r,\ l \le b \le r$ рівна $C(r, r) - C(l-1, r) - C(r, l-1) + C(l-1, l-1)$. У задачі просять знайти такі пари, що $a \le b$. Зауважимо, що існує лише одна пара з $a = b$ — $(0, 0)$. При $a \ne b$ буде враховано пари $(a, b)$ та $(b, a)$, проте для відповіді нам треба порахувати таку пару лиш раз, тому поділимо кількість таких пар на 2.

Щоб знайти $C(x, y)$ скористаємося методом динамічного програмування. Будуватимемо два числа одночасно ідучи від старших бітів до молодших. Використаємо принцип динамічного програмування, де будуть три стани — кількість вже розглянутих бітів, чи перше число вже є меншим за $x$ та чи є друге число вже меншим за $y$. Додаючи новий біт потрібно враховувати, що ми не можемо поставити одиничний біт в обидва числа одночасно, а також не можемо зробити число більшим за його обмеження. Cкладність — $O(\log r)$.

Код розв’язку C++

F. Перетин многокутників.

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

Назвемо координату $x$ цікавою, якщо існує принаймні одна вершина многокутника чи точка перетину двох відрізків, що має таку координату по осі абсцис.

Розглянемо незалежно кожну вертикальну смужку між послідовними цікавими координатами. Знайдемо усі ребра многокутників, що проходять через цю смужку й впорядкуємо їх у порядку зростання ординати точки, що належить цьому ребру і має значення абсцис-координати рівне середині смужки, що розглядається. Розглядаючи ребра в такому порядку, ми можемо підтримувати кількість многокутників, що покривають трапецію, яка зараз розглядається. Кожне ребро або збільшує цю кількість на одиницю, або зменшує. Це можна однозначно визначити за орієнтацією ребра, так як усі многокутники задані в порядку обходу проти годинникової стрілки.

Код розв’язку C++

G. Компресія

Нехай $s$ — довільний рядок з нулів і одиниць. Нехай $F(s)$ — масив чисел, такий, що перше його число рівне кількості однакових символів на початку рядка $s$, друге число — кількості однакових символів в другій групі і так далі. Наприклад, $F("0001101") = [3, 2, 1, 1]$, а $F("111") = [3]$.

Аналізуючи описані операції, можна зрозуміти, які умови є необхідними й достатніми, щоб з рядку $s$ можна було отримати рядок $t$:

Перші символи рядків мають бути рівними.
Довжини масивів $F(s)$ та $F(t)$ мають бути однаковими, адже ми ніяк не можемо змінити кількість груп однакових символів в рядку.
Розміри перших груп обох стрічок мають бути рівними: $F(s)_1 = F(t)_1$.
Аналогічно, розміри останніх груп мають бути рівними: $F(s)_{|F(s)|} = F(t)_{|F(t)|}$.
$F(s)_i \ge F(t)_i$ для всіх $i$, адже ми не можемо добавляти нових символів.
$F(s)_i \equiv F(t)_i\ (mod\ 2$) для $i=2..|F(s)|-1$, адже обидві операції не змінюють парність розміру кожної групи.

Очевидно, що функції $F$ і усі необхідні перевірки можна реалізувати з лінійною складністю.

Код розв’язку C++

H. Фотографії

Виконаємо перші $m$ кроків і будемо перевіряти, чи Зеник не вийшов за межі многокутника і якщо таке відбулося, то ми знайшли відповідь. Нехай $P_i$ — позиція Зеника після виконаних $i$ кроків, де $i = 0..m$. Після $j = k \cdot m + r$ кроків ми опинимось у точці $k \cdot \overrightarrow{P_m} + \overrightarrow{P_r}$.

Якщо $|\overrightarrow{P_m}| = 0$, Зеник буде циклічно ходити по тих самих точках і відповідь — -1. У випадку $|\overrightarrow{P_m}| > 0$, то після кожних $m$ ітерацій Зеник буде зміщуватися на вектор $\overrightarrow{P_m}$, і, рано чи пізно, вийде за межі сногокутника.

Розглянемо остачу $r$ за модулем $m$ і подивимось на позиції Зеника після ходів з індексами $k \cdot m + r$. Якщо розглянути збільшення $k$ від 0 до нескінченності, то спочатку відповідні точки знаходяться всередині многокутника, а після певного моменту — ззовні. Тому можна скористатися двійковим пошуком по $k$, щоб знайти першу точку з остачею $r$, яка знаходиться зовні многокутника. Знайдемо всі такі точки для кожної остачі $r$ від 0 до $m-1$. Відповідь буде індекс найменшої з них.

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

Перевірити, чи точка $B$ належить опуклому многокутнику, можна за логарифмічну складність:

Знайдемо найлівішу точку многокутника, якщо таких декілька, то найнижчу, назвемо її $A$.
Інші вершини многокутника будуть посортовані за полярним кутом відносно точки $A$.
Для заданої точки $B$ бінарним пошуком за полярним кутом можемо знайти дві сусідні вершини многокутника $L$ та $R$, такі що полярний кут точки $B$ відносно точки $A$ лежить між полярними кутами $L$ і $R$.
Перевіримо, чи точка $B$ лежить всередині трикутника $ALR$.

Отож, вибравши мінімальну відповідь серед усіх остач $r$ ми отримуємо повний розв’язок з асимптотичною складністю $O(m \log{n} \log({max\_coord}))$.

Цей розв’язок можна оптимізувати, забравши з асимптотики один з логарифмів. Залишаємо це покращення для читачів вправою на домашнє завдання.

Код розв’язку C++

I. Дерево мінімальної глибини.

Побудуємо незважений орієнтований граф з $n$ вершин. Ребро $(a, b)$ існує в графі, якщо виконується хоч одна з двох умов:

$a$ є батьком вершини $b$ у початковому дереві.
Серед дозволених операцій є операція $(a, b)$.

Нехай $D_i$ — найкоротша відстань від вершини 1 до вершини $i$ у вищеописаному графі. Максимальне з усіх значень $D_i$ і є відповіддю на задачу. Усі $D_i$ можна знайти за допомогою пошуку в ширину з лінійною складністю.

Код розв’язку C++

J. Нульовий масив

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

Скільки кроків потрібно зробити?

Легко показати, що максимальний елемент масиву зменшуватиметься щонайменше на половину на кожному кроці (так як ми точно можемо знайти відрізок з середнім як мінімум $\frac{\max a_i}{2}$). А тому кількість кроків обмежена логарифмічним порядком.
Як ефективно шукати відрізок з найбільшим середнім значенням?

Покажемо, що оптимальний відрізок має довжину 2 або 3. Розглянемо довільний відрізок довжини не менше 4. Нехай його середнє арифметичне рівне $x$. Глянемо на середнє арифметичне перших двох елементів цього відрізка. Якщо воно є більшим чи рівним за $x$, то ми знайшли менший відрізок, довжини два, який має не гірше значення. Якщо ж середнє арифметичне перших двох елементів є строго меншим за $x$, то середнє арифметичне решти елементів має бути більшим за $x$. Цей факт легко довести самостійно, а тому ми опустимо деталі в цьому розборі. Таким чином, ми показали що для будь-якого відрізка дожини щонайменше 4, можна знайти коротший відрізок з не меншим середнім значенням. Тому, щоб знайти оптимальний відрізок досить перевірити лише усі відрізки довжини два та три.

Сумарна складність розв’язку — $O(n \log(\max a_i))$.

Код розв’язку C++

K. Запити на масиві

Нехай $f(a, b)$ — індекс першого біта (в порядку від старших бітів до молодших), в якому число $a$ відрізняється від числа $b$. Вважатимемо, що $f(a, a) = -1$. Також, нехай $a[i]$ — це значення $i$-го біту числа $a$ (0 або 1).

Нехай $C_{l, x, r, y}$ — кількість таких $i$ від 2 до $n - 1$, що $f(a_{i-1}, a_i) = l, f(a_i, a_{i+1}) = r, a_i[l] = x$ та $a_i[r] = y$ у початковому масиві. Усі такі значення легко обчислити з складністю $O(n \log \max a_i)$.

Зауважимо, що кількість локальних максимумів до виконання запитів є рівною $\sum_{i=1}^m \sum_{j=1}^m C_{i, 1, j, 1}$, де $m$ — кількість бітів у найбільшому числі з вхідних даних.

Після виконання операції xor, номер першого біта в якому відрізняються сусідні числа не змінюється, а змінюються лише значення цих бітів. Зокрема, не важко зрозуміти, що якщо ми виконуємо $xor\ x$ для всіх елементів масиву початкового масиву, то кількість локальних максимумів становитиме $\sum_{i=1}^m \sum_{j=1}^m C_{i, x[i] \oplus 1, j, x[j] \oplus 1}$. Цей факт дає повний розв’язок з складністю $O(n \log(\max a_i))$.

Код розв’язку C++

A. Безцінна канапка

Ціна однієї канапки $price = a + 2 \cdot b + c$. Отже відповідь до задачі це $\lfloor \frac{s}{price} \rfloor$ (ділення націло).

Код розв’язку C++

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

B. На човні у магазин

Об’єм води за годину в Дністрі після $i$-того села — це сума об’єму води за годину яка була в Дністрі до $i$-того села та у всіх струмках які втікають безпосередньо перед $i$-тим селом. Таку суму потрібно порахувати для кожного села. Зауважте, що об’єм води може перевищувати розмір 32-бітного типу даних (для прикладу, int в C++), тому для суми тут потрібно використовувати 64-бітний тип даних (long long в С++).

Код розв’язку C++

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

C. В гостях у Марічки

Зауважимо, що рядок kanapka починається та закінчується на підрядок ka. Щоб отримати два входження рядка kanapka оптимально буде накласти початок другого входження на кінець першого, отримавши рядок kanapkanapka. Щоб отримати третє входження можна просто додати рядок napka і отримати kanapkanapkanapka.

Формалізуємо алгоритм:

утворюємо один рядок ka,
поки можемо, дописуємо рядки napka до кінця рядка.

Позначимо кількість символів k, a, n та p — $cntK$, $cntA$, $cntN$ та $cntP$ відповідно.

Тоді максимальна кількість входжень буде рівна $\min (cntK-1, \lfloor \frac{cntA - 1}{2} \rfloor, cntN, cntP)$ якщо є хоча б по одному входженню букв k та a.

Якщо ж в рядку немає букви k чи букви a, то відповідь на задачу 0.

Код розв’язку C++

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

D. Похід за інгредієнтами

Очевидно, що Зенику варто піти або в супермаркет, або відвідати магазин кожного типу окремо, оскільки якщо Зеник відвідав супермаркет, то йому вже не потрібно йти ще в якийсь магазин. Отже задача зводиться до двох випадків: коли Зеник йде в супермаркет, або коли Зеник купує продукти у всіх магазинах окремо.

Розгляньмо випадок, коли Зеник йде до супермаркету. Оскільки ми хочемо мінімізувати відстань до координати 0, то варто вибрати супермаркет який найближчий до цієї координати. Тому нам потрібно вибрати такий супермаркет, в якого мінімальне значення $|d_i|$. Це можна зробити за $O(n)$.

Тепер розгляньмо випадок коли Зеник купує всі продукти в різних магазинах. Як порахувати відповідь коли ми маємо лише по одному магазину кожного типу? Знайдімо найправішу координату і найлівішу. Позначимо координати хлібного, м’ясного та сирного магазинів як $a$, $b$ та $c$ відповідно. Легко зрозуміти що координата найлівішої точки це $l = \min (a, b, c, 0)$, а найправішої $r = \max (0, a, b, c)$. Щоб оптимально обійти їх нам потрібно спочатку піти в один бік, повернутися додому, піти в інший бік і знову повернутися додому. Отже відповідь для випадку магазинів різних типів буде $(|l| + r) \cdot 2$.

Що робити якщо магазинів багато? Ми можемо перебрати магазин кожного типу в який піде Зеник і таким чином знайти відповідь. Такий алгоритм праюватиме за $O(n^3)$, що занадто повільно. Цей алгоритм легко оптимізувати.

Розглянемо магазини одного типу. Якщо є якісь два магазини з додатніми координатами, то нам ніколи не буде вигідно йти до магазину який знаходиться далі від нас, тому його не потрбіно перебирати. Аналогічні міркування справджуються і для магазинів з від’ємними координатами. В результаті, для кожного типу магазинів нас цікавлять лише два магазини: найближчий до нас з додатньою координатою і найближчий з від’ємною координатою. Після того як ми викинемо решту магазинів, всього їх залишиться не більше ніж 6: по 2 кожного типу. Тепер для кожного типу магазинів можемо перебрати до якого підемо, тому що різних таких комбінацій буде не більше ніж $2 \cdot 2 \cdot 2 = 2^3 = 8$.

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

Загальна складність алгоритму $O(n + 2^3)$.

Код розв’язку C++

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

A. Добра справа

Зеник спочатку задонатив $b$ гривень, а потім $k$ разів по $x$ гривень. Тобто, можна записати це формулою $b + k \cdot x$. Отже, в задачі було достатньо запрограмувати таку формулу.

Як альтернативний розв’язок можна було $k$ разів додати $x$ до відповіді за допомогою циклу.

Код розв’язку C++

Код розв’язку C++ з циклом

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

B. Складний екзамен

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

Код розв’язку C++ з рядками

Код розв’язку C++

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

C. Тренування коней

Спочатку навчимось перевіряти чи Петро зможе дійти до зупинки не пізніше ніж до неї приїде трамвай. Для обрахунку часу потрібно поділити відстань на швидкість. Використовуючи цю формулу знайдемо витрачений час трамваю та час Петра. З обмежень задачі можна помітити, що отримані часи будуть цілими. Отже для точності розв’язку будемо обраховувати їх діленням націло.

Для кожної зупинки ми дізнаємось чи Петро може до неї дійти і встигнути на трамвай. Якщо він зможе дійти до двох зупинок, тоді необхідно додатково перевірити до якої зупинки йому ближче. Він піде до першої зупинки, якщо до неї відстань не більша ніж до другої. У випадку якщо він зможе дійти лише до однієї зупинки, то нам потрібно визначити до якої саме. Якщо ж не може дійти до жодної тоді він не встигне на тренування.

Код розв’язку C++

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

D. Забудькуватий Зеник

Порахуємо кількість різних PIN-кодів. Ми знаємо що кожну цифру можна вибирати двома способами. Також обираємо їх незалежно одну від одної. Тому відповідь це добуток кількості варіантів для кожної з цифр, що в даному випадку дорівнює $2^n$.

Якщо перебрати усі можливі пари PIN-кодів і виконати для них відповідну операцію, то необхідно порахувати скільки раз ми отримали рядок $x$. Такий розв’язок пройде приклади та перший блок тестів.

Якщо ми переберемо тільки перший PIN-код, то, згідно умови, можемо однозначно знайти другий. Це можна зробити таким чином: якщо в рядку $x$ на $i$-тій позиції цифра 0, то в другому PIN-коді ставимо таку ж цифру як і в першому. Якщо ж на $i$-тій позиції 1, то змінимо цифру з першого PIN-коду на протилежну. Отже, ми можемо згенерувати всі PIN-коди довжини $n$ і кожен з них буде першим PIN-кодом рівно в одній парі, що нам підходить. Такий розв’язок пройде другий блок тестів.

Оскільки кожен PIN-код утворить одну пару, що нам підходить, а кількість PIN-кодів $2^n$, то й відповідь до задачі $2^n$.

Тому для повного розв’язку задачі достатньо вивести $2^n$.

Код розв’язку C++

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

E. Війна

Перший блок тестів можна розвязувати такими способами:

Для кожного дня порахуємо кількість регіонів з міст під контролем 47-ляндії. Для цього будемо ітеруватись по містах. Якщо ми зустрічаємо місто під контролем 47-ляндії, яке ми ще не відвідували, то обійдемо усі досяжні з нього міста підконтрольні 47-ляндії. Тепер усі ці міста є відвіданими і більше цей регіон не буде врахований. Таким чином після кожного дня ми можемо порахувати відповідь. Складність такого алгоритму буде рівна $O(q \cdot n)$.
Для кожного міста, будемо пам’ятати значення $cnt_v$ — скільки в неї є сусідініх міст під контролем 47-ляндії. Тоді коли місто перестає бути підконтрольним 47-ляндії то замість одного регіону, ми отримуємо $cnt_v$ регіонів. Кожне сусіднє місто буде в своєму окремому регіоні. І навпаки якщо місто стає підконтрольним 47-ляндії, то $cnt_v$ регіонів об’єднаються в один. При зміні стану міста оновимо значення $cnt$ для кожного сусіднього міста. Такий розв’язок має складність рівну $O(q \cdot n)$.

Розглянемо країну як структуру дерево. Візьмемо одне з міст як корінь цього дерева, кожна вершина в цьому дереві, крім кореня, має батька. Тепер замість $cnt_v$, пам’ятатимемо $son_v$ — кількість синів даної вершини під контролем 47-ляндії. Для того аби визначити $cnt_v$ нам достатньо перевірити чи батько даної вершини належить 47-ляндії. А решта сусідніх міст є синами поточної вершини, ми знаємо скільки серед них належать 47-ляднії — $son_v$. У випадку коли батько належить 47-ляндії, тоді $cnt_v = son_v + 1$, у іншому варіанті $cnt_v = son_v$. Тепер якщо вершина змінює свій стан тоді ми маємо оновити значення $son$ для її батька, якщо звісно він існує. Тоді кожна така операція працює за $O(1)$, а сумарна складність запитів рівна $O(q)$. Також необхідно порахувати початкові значення $son_v$, що ми можемо зробити за $O(n)$ звичайним пошуком вглиб, або певними формулами.

Код розв’язку C++ $O(n \cdot q)$

Код розв’язку C++

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

F. Надскладне завдання

Переберемо всі підрядки рядка $s$. Для кожного такого підрядка переберемо всі підрядки $t$ і порівняємо їх на рівність. Такий розв’язок працюватиме за $O(|s|^2 \cdot |t|^2 \cdot cmp)$, де cmp — час порівняння двох підрядків, що в найгіршому випадку рівне $O(|t|)$. Цей розв’язок пройде перший блок тестів.

Розглянемо швидший розв’язок. Переберемо всі підрядки рядка $t$ і запишемо їх в мультимножину. Тепер для кожного підрядка $s$, замість того щоб перебирати підрядок в $t$, просто подивимося скільки таких підрядків є в нашій мультимножині. Такий розв’язок працюватиме за $O((|t|^2 + |s|^2) \cdot log(|t|^2) \cdot cmp)$, де cmp — час порівняння двох підрядків, що в найгіршому випадку рівне $O(|t|)$. Цей розв’язок пройде два перші блоки тестів.

Тепер розглянемо розв’язок, який розв’яже задачу з повними обмеженнями. Нехай ми знайшли підрядки з рядків $s$ та $t$ які співпадають. Очевидно, що всі їхні відповідні рядки також співпадають. Якщо довжина підрядків які співпадають рівна $n$, то можна до відповіді додати $\frac{n \cdot (n + 1)}{2}$ і вже не розглядати їх підрядки. Тоді якщо ми співставимо $s$ і $t$ у всіх можливих позиціях і знайдемо проміжки де рядки співпадають, то зможемо легко порахувати відповідь.

Наприклад якщо $s$ = aabcabb, а $t$ = abba, то один з варіантів співставлення виглядатиме так:

Тут є підрядки довжин 2 та 1, тому до відповіді треба додати $\frac{2 \cdot 3}{2} + \frac{1 \cdot 2}{2} = 3 + 1 = 4$. Зауважимо, що рядок $t$ може виходити за межі $s$, наприклад так:

Оскільки в нас є $|s| + |t| - 1$ позиція для того щоб їх співставити, то загальна складність такого алгоритму буде $O((|s| + |t|) \cdot |t|)$.

Код розв’язку C++

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

G. Викладацька майстерність

Розглянемо перший блок тестів, у ньому нам потрібно заповнити прямокутник розміру $1 \times (n - b[i])$, тому навчимось розвязувати задачу заповнення коли в нас є прямокутник розміру $1 \times m$. Для цього розглянемо найправішу плиточку, що буде стояти в цьому прямокутнику. Вона може бути розміру 1 або розміру 2. Поставивши одну з цих плиточок в нас залишиться прямокутник розміру $1 \times (m - 1)$ або $1 \times (m - 2)$ відповідно. Визначимо $f[m]$, як відповідь на задачу для прямокутника розміру $1 \times m$. Тоді можна записати таке рівняння: $f[m] = f[m - 1] + f[m - 2]$, а значення $f[0]$ і $f[1]$ рівні 1. Цей масив можна обрахувати звичайним циклом.

Перейдемо до другого блоку, нам потрібно заповнити прямокутник розміру $2 \times (n - a[i])$, тобто потрібно вміти розвязувати задачу заповнення для прямокутника $2 \times m$. Для цього введемо два масиви $g[m]$ — відповідь на задачу для прямокутника розміру $2 \times m$, та допоміжний $h[m]$ — відповідь на задачу для фігури зображеної нижче, зрозуміло що відповідь буде аналогічна якщо зверху буде більша кількість вільних клітинок.

Спробуємо для них написати рівняння подібно до першого блоку, для цього розглянемо як зліва будуть замощені плиточки , спочатку для $h[m]$. Для цієї фігури є два варіанти яка плиточка знаходиться в найлівішій вільній клітинці:

Якщо ставимо плитку розміру 1, то переходимо до задачі $g[m - 1]$, якщо ж розміру 2 то до задачі $h[m - 1]$, тому формула $h[m] = g[m - 1] + h[m - 1]$. Тепер розглянемо задачу $g[m]$.

Тепер розглянемо усі можливі варіанти плиточки що буду покривати ліву нижню клітинку:

У перших двох варіантах ми переходимо до задач $h[m]$ і $g[m - 1]$ відповідно. Для третього варіанту:

Розглянемо варіанти плиточки для лівої верхньої клітинки.

Тобто переходимо до задач $h[m - 1]$ і $g[m - 2]$ відповідно. А отже кінцева формула буде такою: $g[m] = h[m] + g[m - 1] + h[m - 1] + g[m - 2]$. Отже ми можемо ці відповіді порахувати в циклі, спочатку рахуємо $h[m]$ потім $g[m]$.

Зауважимо що $g[1]$ рівне 2, бо ми можемо взяти дві плиточки розміру 1 або одну розміру 2. А $g[0]$ рівне 1, бо ми нічого не ставимо, як і було сказано в примітках. Значення $h[1]$ буде рівне 1, бо ми можемо поставити лише одну пличотку. Зрозуміло, що $h[0] = 0$, бо такої фігури не існує, а отже її не можна заставити плиточками.

Повернемось до початкової задачі. Без обмежень загальності, нехай у верхньому рядку потрібно закласти $m$ клітинок, а у нижньому на $d$ більше.

Тепер розглянемо межу між прямокутником ширини 1 і прямокутником ширини 2. Розглянемо варіант коли там стоїть плиточка розміру 2.

У такому варіанті зліва в нас задача $f[d - 1]$, а справа $h[m]$ і ці задачі незалежні, тобто для кожного способу зліва можна вибрати будь-який спосіб справа, тому кількість варіантів рівна добутку цих двох величин. Зауважимо, що цей варіант можливий лише за умови $d \geq 1$ і $m \geq 1$, для того аби плиточка розміру два мала клітинки на які її ставитимуть.

Якщо ж на межі не було плиточки довжини 2, то в нас будуть дві незалежні задачі, одна виділена синім, а інша жовтим.

Тоді відповідно в нас є задача $f[d]$ і $g[m]$, аналогічно до попереднього варіанту до відповіді потрібно додати добуток цих величин. Отже, відповідь на задачу буде рівна $g[m] \cdot f[d] + h[m] \cdot f[d - 1]$.

Код розв’язку C++

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

A. Вороги

У даній задачі необхідно знайти за скільки днів закінчаться солдати в кожній ворожій країні. І взяти максимум з цих значень, тобто $max(\frac{A}{C}, \frac{B}{D})$. Врахуйте те що результат є цілим числом і тому можна використовувати цілочисельне ділення.

Код розв’язку C++

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

B. Втрати ворога

Якщо ми порахуємо суму втрат за $n - 1$ день, тоді різниця загальних втрат і цієї суми буде рівна кількості втрат в загублений день. Зауважте, що якщо отримане число не є додатнім, тоді Зеник допустив десь помилку.

Код розв’язку C++

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

C. Портрети

Враховуючи умову про те що вантажівка може за один раз доставляти незвичні матеріали лише в один рядок, нам необхідно для кожного рядка порахувати мінімальну кількість поїздок аби розставити потрібні матеріали. У кінці отримані значення для рядків необхідно буде просумувати. Зауважимо, що для рядка нам не важливо де знаходяться «*», а цікавить лише їх кількість — $cnt$. Тоді будемо жадібно возити матеріали, веземо повну вантажівку з $k$ одиницями матеріалу, або ту кількість що залишилась. Також цю кількість можна було порахувати формулою $\lceil\frac{cnt}{k}\rceil$, цю формулу можна рахувати використавши цілочисельне ділення в формулі $\lfloor\frac{cnt + k - 1}{k}\rfloor$.

Код розв’язку C++

Код розв’язку C++ з формулою

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

D. Нові втрати ворога

Для того аби отримати хоча б 10 балів було достатньо відтворити процес вказаний в умові, тобто ітеруємось по масиву, щоб знайти сусідні клітинки з найбільшою різницею і поміняємо місцями їх значення. Цей процес будемо робити поки масив не стане посортованим. Проте такий розв’язок є доволі повільним. Тому необхідно зауважити, що якщо є два елементи $i$ та $j$ для яких виконується $i < j$ та $a_i > a_j$, тоді колись ми їх поміняємо місцями. А пару елементів для якої виконується $i < j$ та $a_i < a_j$ ми ніколи не будемо міняти місцями. Отже, задача зводиться до того аби порахувати кількість інверсій, тобто кількість таких пар $i < j$, що $a_i > a_j$. І це можна зробити використавши два вкладені цикли по $i$ та по $j$.

Код розв’язку C++

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

E. Хаймарс

Перш за все впорядкуємо військові об’єкти за відстанню від початку колони. Оскільки об’єкти не рухаються, то нема змісту обстрілювати одну ділянку більше одного разу.

Використаємо підхід динамічного програмування. Будемо знищувати об’єкти зліва направо. Стан буде характеризуватися кількістю знищених військових об’єктів від початку колони $cnt$. Також, враховуючи те що в нас є обмеження на кількість пострілів з хаймарсу, це теж необхідно вказати в стані динаміки. А отже наша динаміка виглядатиме так: $dp[cnt][himars]$ — мінімальна кількість пострілів, щоб знищити перші $cnt$ об’єктів зробивши при цьому рівно $himars$ пострілів з хаймарсу. Тоді, для того аби перерахувати цю динаміку, будемо вважати що останній зроблений постріл має правий кінець рівно в позиції $cnt$-го об’єкту. Усі об’єкти з координатою в проміжку $[a_{cnt} - x, a_{cnt}]$ будуть знищені з граду і $[a_{cnt} - y, a_{cnt}]$ з хаймарсу. А отже нам потрібно для кожного варіанту пострілу знайти найлівіший об’єкт який буде обстріляний цим пострілом. Це можна зробити двійковим пошуком, або методом двох вказівників, оскільки це не залежить від змінної $himars$. Тоді ми знаємо скільки зліва залишиться об’єктів, також нам відомо для них значення динаміки, тобто найменшу кількість пострілів щоб знищити цей префікс. Зрозуміло, що постріл з хаймарсу можна зробити лише якщо $himars > 0$ і тоді значення динаміки буде мінімумом з двох варіантів пострілу.

Для того аби знайти відповідь на задачу потрібно перебрати $himars$ — яку кількість пострілів з хаймарсу ми зробимо. Відповідь буде рівна мінімуму серед значень динаміки $dp[n][himars]$.

Код розв’язку C++

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

F. Волонтерство

Використаємо алгоритм Дейкстри. Для кожного міста $v$ будемо підтримувати $D[v]$ — поточний мінімальний час за який туди можна потрапити з першої вершини. Початково значення $D[v]$ встановимо достатньо великим числом.

Візьмемо місто, серед ще не розглянутих, з найменшим часом. Спробуємо через дане місто доїхати до сусідніх міст, які з’єднані прямою дорогою $e$ з даним містом. Порахуємо найменший момент часу у який ми зможемо доїхати до сусіднього міста по даній дорозі. Для цього подивимось коли ми зможемо поїхати по даній дорозі і не потрапити під обстріл. Оскільки обстріли зациклені, то ситуація на цій дорозі в момент часу $D[v]$ така ж як і в момент часу $t = D[v] \mod (c[e] + d[e])$, де $\mod$ рахує остачу від ділення. Якщо зараз дорога обстрілюється ($t < c[e]$), то ми повинні зачекати до перезарядки і почати рух в той момент коливона почнеться. Якщо ж дорога не обстрілюється ($c[e] \le t$), то нам необхідно перевірити чи ми встигнемо доїхати до початку нового обстрілу ($t + l[e] \le c[e] + d[e]$). Якщо встигаємо то просто їдемо і доїжджаємо в момент часу $D[v] + l[e]$, інакше необхідно чекати коли наступний обстріл закінчиться і тоді їхати. Зауважимо, що якщо для того аби проїхати по дорозі нам необхідно більше часу ніж час перезаряджання, тоді ми ніколи не зможемо по цій дорозі проїхати. Цей процес будемо продовжувати поки у нас залишаються ще нерозглянуті міста.

Код розв’язку C++

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

G. Пес Патрон

Зауважимо, що нам цікаво лише які клітинки, з мінами і журналістами, ми відвідували і в якій клітинці ми зараз стоїмо. Використаємо підхід динамічного програмування. Будемо підтримувати бітмаску розміру $2 \cdot k$ для тих клітинок які вже відвідані, а також в якій клітинці з $2 \cdot k$ цікавих ми стоїмо. Значення динаміки $dp[mask][v]$ — найкоротша відстань щоб пройти від стартової клітинки по відвіданих клітинках в $mask$ і остання клітинка в якій ми зупинимось буде $v$. Для обрахунку цієї динаміки переберемо з якої клітинки ми прийшли і серед усіх варіантів знайдемо мінімум. Зауважимо, що стан з якого ми прийшли буде містити на 1 біт менше у своїй бітмасці, і буде мати значення бітмаски менше. Тому якщо ми перебиратимемо маски по зрозстанню, то для обрахунку поточного значення будемо використовувати вже обраховані значення динаміки.

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

Зауважимо, що для пришвидшення цієї динаміки можна пропускати недосяжні стани, наприклад, якщо пес Патрон відвідав більше журналістів ніж мін.

Код розв’язку C++

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

A. Найкраща гвинтівка

Зеник з $i$-ої гвинтівки може вистрілити $\lfloor \frac{x}{b_i} \rfloor + 1$ разів. Тому нам необхідно помножити це число на $a_i$, щоб порахувати шкоду, що може нанести $i$-а гвинтівка. Отже, в задачі необхідно знайти гвинтівку з найбільшим таким значенням.

Код розв’язку C++

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

B. Привид Києва

Для того аби знищити $i$-тий ворожий літак Зенику необхідно нанести $\lceil \frac{h_i}{a} \rceil$ ударів. І щоб Зеника не підбили його літак повинен витримати вистріли у відповідь, таких вистрілів буде $\lceil \frac{h_i}{a} \rceil - 1$. А сумарна шкода літаку Зеника за цей двобій буде рівна $(\lceil \frac{h_i}{a} \rceil - 1) \cdot d_i$. Отже, будемо пам’ятати скільки міцності в літака Зеника ще залишилось і будемо віднімати сумарну шкоду. Якщо після якогось повітряного бою в нього вийшла міцність менша або рівна за 0, тоді літак Зеника не зможе вціліти і відповідь тоді No. А якщо ж такого не сталось, то його літак цілий і у відповідь необхідно вивести Yes.

Код розв’язку C++

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

C. Розподіл

Використаємо жадібний підхід. Для взводів, що мають однакову найменшу кількість людей, дамо по одному ящику з боєприпасами. Для взводів з другим найменшим значенням дамо по 2 ящики з боєприпасами і так далі. Тобто впорядкуємо взводи за кількістю людей в них. Перший з них отримає 1 ящик з боєприпасами. Далі ітеруємось по взводах від другого, якщо в даного взводу така ж кількість людей як в попереднього то дамо йому стільки ж якщиків як і попередньому взводу. Інакше необхідно дати на 1 ящик більше.

Зауважте, що відповідь може бути більшою за $5 \cdot 10^9$, а отже необхідно використовувати тип даних, що дозволяє працювати з такими великими значеннями.

Код розв’язку C++

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

D. Важка робота волонтерів

У нас є два варіанти в яку сторону буде відправлена посилка: вліво або вправо. Розглянемо випадок, коли посилка буде відправлена вправо ($a_i < b_i$). Інший варіант буде аналогічно розв’язуватись. Отже, для того аби доставити таку посилку ми маємо спочатку відвідати позицію $a_i$, а потім $b_i$. Припустимо, що ми можемо доставити певним чином посилку, тоді розглянемо останній раз коли ми були в клітинці $a_i$ перед тим як доставити посилку. Ми повинні іти вправо з цієї клітинки, тобто мала існувати така ключова позиція $x_j$, що існує наступна позиція $x_{j+1}$ і виконується нерівність $x_j \le a_i < x_{j+1}$. Аналогічно зробимо для $b_i$, але ми розглянемо перше відвідування $b_i$ після того як взяли посилку в $a_i$. Тоді ми мали прийти в позицію $b_i$ зліва, тобто має існувати такий момент $x_k$ для якого існує $x_{k-1}$ і виконується нерівність $x_{k-1} < b_i \le x_k$. Отже, якщо існують два таких індекси $j$ та $k$ для яких виконується $x_j \le a_i$, $b_i \le x_k$ та $j < k$ — умови того, що ми з $a_i$ підемо вправо, в $b_i$ прийдемо зліва і відповідно що посилку ми візьмемо швидше ніж доставимо її. Якщо таких індексів не існує, то ми не зможемо доставити посилку. У випадку якщо $b_i < a_i$ нам потрібно знайти індекси $j$ та $k$ для яких виконуються умови $a_i \le x_j$, $x_k \le b_i$ та $j < k$.

Для того аби перевірити чи існують потрібні індекси знайдемо найменше $j$ для якого буде виконуватись умова між $a_i$ та $x_j$ ($x_j \le a_i$ або $a_i \le x_j$). Аналогічно знайдемо найбільше $k$ для якого буде виконуватись умова між $b_i$ та $x_k$ ($b_i \le x_k$ або $x_k \le b_i$). Якщо відповідні індекси існують і для них виконується $j < k$, тоді посилку можна доставити. Отже, такий розв’язок буде працювати за $O(m \cdot n)$, бо для кожної посилки нам потрібно перебрати індекс ключової позиції.

Для пришвидшення попереднього розв’язку посортуємо $n$ пар ($x_{ind}$, $ind$), тоді кожна умова буде виконуватись для певного префіксу або суфіксу цього масиву. Оскільки нам потрібно мінімум і максимум, то створимо масив в якому будемо пам’ятати, на кожному префіксі та кожному суфіксі, мінімальне та максимальне значення другого параметру з пари. А визначати для якого префіксу або суфіксу виконується умова, можна за допомогою двійкового пошуку.

Код розв’язку C++

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

E. Байрактар

Для зручності відсортуємо вантажівки по їх координаті.

Для того аби отримати бали за два найлегших блоки необхідно було перебрати вантажівку в яку ми вистрілимо і відтворити процес вибухів. Наприклад, для цього можна підтримувати проміжок $[l, r]$, де усі вантажівки в цьому проміжку вибухнуть. Проте на цьому проміжку могли бути вантажівки які ми ще не розглянули, такі вантажівки можуть оновити значення $l$ і $r$. У простішому блоці можна було проітеруватись по усіх вантажівках і подивитись чи вони в проміжку і ми їх ще не розглнули. Для другого блоку процес пошуку не розглянутих вантажівок необхідно пришвидшити. Наприклад, можна пам’ятати впорадковану множину або використати метод двох вказівників

Для того аби розв’язати задачу зауважимо, що якщо відрізок вибуху вантажівки $[a_j - b_j, a_j + b_j]$ є вкладений у відрізок вибуху іншої вантажівки $[a_i - b_i, a_i + b_i]$, тоді нам не вигідно стріляти в $j$-ту вантажівку, бо $i$-та підірве не менше вантажівок. Якщо ми не будемо пробувати підривати такі вантажівки як $j$-та, тоді вибух буде поширюватись незалежно вліво та вправо. Тобто, якщо ми детонацією зачепимо вантажівку справа, то вибух від неї пошириться не лівіше ніж був до того. А отже, ми маємо окремо порахувати скільки вантажівок ми підірвемо зліва і скільки справа, якщо вибухи незалежні. Тобто, вибухи $i$-ї вантажівки відбуваються у проміжку $[a_i - b_i, a_i]$ та $[a_i, a_i + b_i]$, відповідно для вибухової хвилі вліво і вправо. Для розвязання таких підзадач використаємо підхід динамічного програмування. Нехай $L[i]$ — номер найлівішої вантажівки що ми можемо підірвати вибуховою хвилею вліво, якщо $i$-та вибухне. Аналогічно $R[i]$ — номер найправішої вантажівки у випадку вибуховою хвилею вправо. Щоб обрахувати $L[i]$ нам необхідно знайти найменше значення $L[j]$ для якого виконується $a_i - b_i \le a_j \le a_i$. Аналогічно, щоб обрахувати $R[i]$ нам необхідно знайти найбільше значення $R[j]$ для якого виконується $a_i \le a_j \le a_i + b_i$. Такі значення можна знайти за допомогою структур даних, які вміють шукати мінімум на відрізку, і змінювати значення в точці. Наприклад, можна використати дерево відрізків. Маючи такі значення, ми знаємо, що підірвавши $i$-ту вантажівку, відповідь буде $R[i] - L[i] + 1$. Відповіддю на задачу буде максимум з таких значень.

Зауважимо, що якщо вибухи не можна розглядати незалежно, тобто для вантажівок, вибухова хвиля яких є вкладеною, то значення $R[i] - L[i] + 1$ може бути меншим ніж кількість вантажівок, які вибухнуть якщо першою підірвати $i$-ту. Проте, ми показали, що в такі вантажівки стріляти неоптимально, а це означає, що ми можемо проігнорувати це.

Код розв’язку C++

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

F. Бомбардування

Перш за все в цій задачі необхідно було зрозуміти, що в нас задано кореневе дерево. Тоді дороги з даної вершини до вершин східніше це теж саме, що й ребра до синів в дереві. Отже, наш запит перетворюється у такий: порахуйте суму вершин в піддереві вершини $v_i$ на відстані не більше $d_i$.

Тоді для зручності порахуємо $h[i]$ — глибину $i$-ї вершини, тобто відстань до кореня дерева. Для цього напишемо, наприклад, обхід в глибину. Тоді вершини в піддереві будуть мати глибину більшу ніж в кореня піддерева. А відстань від вершини до її предка рівна різниці їх глибин. А, отже, для того аби отримати бали за перший блок тестів достатньо було написати обхід дерева починаючи з вершини $v_i$ і йдучи у вершини з більшою глибиною. І під час цього процесу додавати до відповіді значення вершини якщо вона має глибину не більшу за $h[v_i] + d_i$. Такий розв’язок буде мати складність $O(q \cdot n)$.

Для другого блоку тестів потрібно було помітити, що відстань від поточної вершини до усіх інших завжди менша за $n$. Тоді наша задача перетворюється до того, що нам необхідно порахувати суму в піддереві. Що можна було зробити в обході де ми обраховуємо $h[i]$ і запам’ятати в масиві $sum$.

Тепер для блоку без обмежень необхідно помітити, що ми можемо додати значення $sum[v_i]$ і нам потрібно буде відняти значення $sum$ для вершин в піддереві на глибині $h[v_i] + d_i + 1$. Бо вершини на такій глибині не мають бути враховані у відповідь і їхні піддерева теж, оскільки в них глибина ще більша. Якщо ми в початковому обході в глибину будемо додавати вершину в список вершин на такій глибині. Тоді для будь-якої вершини, усі вершини в її піддереві на певній глибині будуть іти підряд у списку для цієї глибини. А отже, нам необхідно знайти проміжок вершин на глибині $h[v_i] + d_i + 1$, що належать піддереву вершини $v_i$ і порахувати їх суму. Порахувати суму можна використавши префіксні суми, бо у нас немає ніяких змін.

Підзадача з пошуком меж проміжку є складнішою, для того аби її розв’язати запам’ятаємо Ейлерів обхід дерева. Це можна зробити в нашому початковому обході в глибину, запам’ятавши для вершини $tin$ та $tout$ — часи коли ми увійшли та вийшли з вершини. Знаючи такі значення ми можемо сказати чи вершина $u$ є строго у піддереві вершини $v$ просто перевіривши $tin[v] < tin[u] < tout[u] < tout[v]$. Тепер ми можемо для глибини рахувати не список вершин, а список значень $tin$ для цих вершин. Тоді такий список буде посортований, оскільки ми додаємо вершини в тому порядку, в якому їх відвідували. У такому списку нам потрібно знайти $l$ — індекс найлівішої вершини на рівні, яка є в піддереві вершини $v$. Тобто таку $u$, в якої мінімальний $tin[u] > tin[v]$. Також нам потрібно знайти такий $r$ — індекс найправішої вершини на рівні, яка є в піддереві вершини $v$. Тобто таку $u$, в якої максимальний $tin[u] < tout[v]$. Це будуть межі відрізка, суму на якому нам потрібно відняти. Щоб знайти такі межі ми можемо використати двійковий пошук по часах входу на відповідному рівні.

Код розв’язку C++

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

G. Важливі цілі

Перш за все у задачі потрібно було помітити те, що радіус $R$ можна шукати двійковим пошуком. Оскільки збільшивши радіус кола ділянка ураження тільки збільшиться і не може втратити зв’язність. Тепер для радіусу $R$ потрібно перевірити чи можна розташувати три кола такого радіусу щоб покрити 3 задані точки і щоб усі кола були з’єднані.

Тоді у нас є два випадки: кожне коло містить точку або одне з кіл містить дві точки. Випадок, коли одне коло може містити 3 точки можна не розглядати, так як ми могли посунути це коло до того моменту коли одна з точок стане ззовні. Тоді помістити її в інше коло і отримати таку ж ситуацію як у другому випадку.

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

Тоді центр такого кола має бути на відстані не більше $R$ до вершини, що воно покриває, бо інакше воно не буде покривати цю вершину. Також відстань до інших двох точок має бути не більше ніж $3 \cdot R$, бо якщо більше, тоді ми не зможемо поставити коло яке буде покривати цю вершину і мати спільну точку на цьому колі. Тепер нам потрібно сказати чи може існувати такий центр кола. Для цього подивимось чи кола радіусів $R$, $3 \cdot R$ та $3 \cdot R$, в заданих вершинах, мають спільну точку. Бо геометричним місцем точок, що не далі ніж на відстані $d$ від даної точки — це коло в даній точці радіусу $d$. Зауважте, що нам потрібно розглянути до якої точки з 3-х заданих відстань має бути менша рівна за $R$, а до інших двох $\le 3 \cdot R$.

У другому випадку ситуація буде подібною, але тут центр кола що містить дві точки має бути на відстані не більше $R$ від цих двох точок. А відстань до третьої має бути не більша за $5 \cdot R$, оскільки ми можемо розмістити коло, що не містить жодну точку, як коло для з’єднання.

Отже, нам необхідно знайти чи кола з радіусами $R$, $R$ та $5 \cdot R$ мають спільну точку. Аналогічно до попереднього варіанту нам необхідно розглянути яка з 3-х точок буде мати коло радіуса $5 \cdot R$.

У двох випадках нам потрібно сказати чи три кола мають хоча б одну спільну точку.

Таку підзадачу можна розв’язати так: розглянемо перетин двох кіл і подивимось чи належить цей перетин третьому колу, якщо так тоді у кіл є спільна точка. Зауважимо, що перетину може й не бути, тоді нічого не будемо перевіряти. Також необхідно розглянути перетин кожної пари кіл. Такий аглоритм буде працювати якщо у нас немає кола яке лежить в іншому. Проте є лише один варіант коли одне коло всередині іншого і існує спільна точка для 3-х кіл, але описаний вище алгоритм скаже протилежне.

Код розв’язку C++

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

A. Фокуси Зеника

Фокус Зеника полягає у тому, що в кінці, після виконання вказаних операцій, буде число 47 для будь-якого початкового числа. Отже, задача зводиться до того аби перевірити чи число $y$ рівне 47. Також можна було просто відтворити операції вказані в умові використовуючи заданий $x$.

Код розв’язку C++

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

B. Цукерочки на олімпіаду

У задачі необхідно максимізувати значення $(a_i + j) - (a_j + i)$. Перегрупувавши доданки в цьому виразі отримаємо $(a_i - i) - (a_j - j)$. Якщо ми позначимо $b_i = a_i - i$, тоді нам необхідно максимізувати $b_i - b_j$. Для того аби максимізувати такий вираз нам необхідно вибрати $b_i$, як максимальне значення в масиві $b$. А $b_j$ вибрати як найменше значення. І як відповідь вивести різницю $b_i - b_j$.

Також зауважимо, що значення $(a_i + j) - (a_j + i)$ буде таке ж якщо в нас індексація масиву починається з нуля або з одиниці.

Код розв’язку C++

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

C. Нудне відкриття

Для того аби здати перший блок тестів достатньо було перебрати усі підвідрізки які є в даному та порахувати для них суму. Відповідь буде рівна кількості тих у яких сума рівна 0. Складність такого розв’язку $O(q \cdot n^3)$, оскільки підвідрізків є не більше ніж $n^2$ і для кожного з них необхідно порахувати суму, що може займати до $n$ операцій.

Щоб здати задачу на повний бал необхідно навчитись рахувати суму на підвідрізку швидше ніж за $O(n)$. Наприклад, це можна зробити порахувавши суму чисел на кожному префіксі. Позначимо суму на префіксі довжиною $i$ значенням $pref_i$. Тоді сума на відрізку від $l$ до $r$ включно буде рівна $pref_{r} - pref_{l - 1}$. Також суму на на відрізку $[l, r]$ можна перерахувати з суми на відрізку $[l, r - 1]$ додавши значення $a_r$.

Код розв’язку C++

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

D. Турнірна таблиця обласної олімпіади

Розглянемо перший блок тестів, де є тільки запити на суму. Учасники не міняються місцями і суму нам необхідно порахувати на певному проміжку учасників, тому ми можемо порахувати значення $pref_i$ — сума номерів перших $i$ учасників. Відповідно $pref_0 = 0$. Тоді сума номерів учасників на відрізку від $l$ до $r$ включно рівна $pref_r - pref_{l - 1}$. Тепер нам необхідно навчитись визначати межі $l$ та $r$ для запиту. Для цього будемо пам’ятати $pos_i$ — позиція учасника з номером $i$. Тоді межі для запиту $x_i$, $k_i$ будуть такі: $l = pos_{x_i} - k_i$ та $r = pos_{x_i} - 1$.

Для блоку тестів, де немає запитів першого типу, помітимо те, що лише дві людини міняються місцями в одному запиті. А отже ми можемо оновити значення $pos$ для цих двох учасників. І зауважимо, те що $pref_i$ змінюється тільки в позиції $pos_{x_i}$, а отже ми її можемо перерахувати.

Тепер для усієї задачі необхідно помітити, що Зеник не може обігнати більше ніж $n + q$ учасників. Це тому, що початково перед ним може бути максимум $n - 1$ учасник, і запит другого типу збільшує це значення максимум на 1. Ми вміємо оновлювати задачу коли учасник обганяє одного перед собою, тобто ми можемо $x_i$ разів зробити так, що Зеник обганяє одного учаника перед собою. Сумарно він обжене не більше $n + q$ учасників, тому сумарна складність $O(n + q)$.

У реалізації винесено у функцію оновлення усіх значень коли учасник $x$ обганяє одного учасника над собою.

Код розв’язку C++

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

E. Не тягніть інтригу

Для того аби розв’язати задачу необхідно помітити, що останнє число ми можемо визначити порахувавши скільки нових інверсій воно створить. Якщо ця кількість $x$, то це означає що лівіше є $x$ чисел більших нього, і відповідно $n - 1 - x$ чисел менших за нього, а отже його значення $n - x$. Ми визначили останнє число і тепер можемо продовжити даний процес для передостаннього числа і так далі. Проте для наступних чисел ми повинні врахувати те, що деякі числа вже встановленні. Тобто якщо ми знаємо, що в нас на певному префіксі має бути $y$ чисел менших за поточне, то нам необхідно вибрати $y + 1$-ше число, яке ще не встановлене. Це можна зробити за $O(n)$. Тоді сумарна складність $O(n^2)$.

Тепер для повної задачі нам потрібно швидко знаходити $y + 1$-ше не використане число. Один із варіантів — це встановити в позиції від 1 до $n$ одиниці, і коли ставимо число, то в його позиції змінюємо 1 на 0. Тепер в нас стоятиме 1 тільки в позиціях чисел, які ще не встановлені. А отже нам потрібно знайти $y + 1$-шу 1-цю. Це є стандартна задача розглянута у відео лекції на тему «Дерево відрізків» на YouTube-каналі Algotester, якщо ми будемо шукати максимальний префікс із сумою $y$. Тоді потрібне нам число знаходитиметься на наступній позиції. Тепер в цій позиції потрібно замінити 1 на 0.

Код розв’язку C++

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

F. Цукерочки для друзів

Розглянемо простий дільник $p$ числа $n$, нехай $b$ — степінь $p$ в факторизації $n$, тобто найбільше ціле число таке що $n$ ділиться на $p^b$. Якщо НСК($n-1, n-2, \dots, n-k$) ділиться на $n$, то це означає що ділиться і на $p^b$. Також можна помітити, що для цього має існувати число, серед $n - 1, n - 2, ..., n - k$, яке ділиться на $p^b$. Нехай це число $n - x$. Тоді оскільки $n$ теж ділиться на $p^b$ тоді з цього випливає, що і $x$ ділиться на $p^b$. А також ми можемо сказати, що $p^b \le x$, а отже число $p^b$ є серед чисел 1, 2, ..., $k$. Отже якщо НСК($n - 1, n - 2, ..., n - k$) ділиться на $n$ тоді і лише тоді, коли НСК(1, 2, ..., $k$) теж буде ділитись на $n$. Значить нам необхідно порахувати кількість дільників числа НСК(1, 2, ..., $k$). Для першого блоку тестів можна було порахувати це число, розглянути усі його дільники $n$ та порахувати скільки з них більші за $k$. Зі збільшенням $k$ це значення буде дуже збільшуватись і такий розв’язок не можна буде використати для всієї задачі.

Для блоку з одним $k$ можна помітити, що якщо ми зможемо представити НСК(1, 2, ..., $k$) у вигляді $p_1^{b_1} \cdot p_2^{b_2} \cdot ... \cdot p_m^{b_m}$, тоді кількість дільників такого числа рівна $(b_1 + 1) \cdot (b_2 + 1) \cdot ... \cdot (b_m + 1)$. А також можна помітити що усі числа від 1 до $k$ є дільниками НСК, тому ми можемо від кількості усіх дільників відняти $k$. У попередньому абзаці ми показали, що НСК може ділитись на якесь $p^b$ лише тоді коли $p^b \le k$. А отже нам достатньо для кожного простого числа $p \le k$ порахувати максимальне $b$ таке, що $p^b \le k$ і порахувати добуток $b + 1$ по модулю.

Щоб розв’язати повністю задачу необхідно зрозуміти що зі збільшенням $k$ для деяких $p$ може збільшитись $b$. Тому будемо опрацювувати запити в посортованому порядку. І посортуємо усі числа вигляду $p^b$, що не перевищують $10^7$. Використавши метод двох вказівників. Коли ми переходимо від одного $k$ до іншого то деякі значення $b$ зміняться, а отже нам потрібно буде оновити відповідь. Нам потрібно поділити на старе значення $b$ + 1 і помножити на нове таке значення. Ділення по модулю на число $x$, яке взяємнопросте з модулем $M = 998244353$ — це те ж що і операція множення на число $y$ таке, що $x \cdot y \mod{M} = 1$. Для простого числа $mod$ ми знаємо малу теорему Ферма: $x^{M - 1} \mod{M} = 1$, а отже $y = x^{M - 2} \mod{M}$ і його можна порахувати швидким піднесенням до степеня. Також оскільки значення $b$ не більші за 23, то можна було порахувати обернене значення для кожного числа від 1 до 23 і записати це в масив.

Код розв’язку C++

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

G. Цукерочки на столі

При додаванні точки знайдемо найкоротшу відстань від неї до всіх інших наявних точок. Тепер перевіримо чи ця відстань менша ніж була перед тим. Також в нас є запити видалення, тому нам треба пам’ятати відповідь для попередньо доданих точок. Для цього можна використати стек — структуру яка може додавати елемент в кінець, видаляти з кінця і знати останній елемент стеку.

Для повної задачі необхідно зауважити те що точок на відстані не більшій ніж $r$ від нової точки, де $r$ — найменша відстань між всіма іншими точками, є небагато, і нам потрібно порахувати відстань тільки до цих кількох точок. Проте шукати точки на відстані не більше $r$ від даної доволі складно, тому будемо шукати точки що знаходяться в квадраті з довжиною сторони $2 \cdot r$ з центром в новій точці. Таких точок не може бути більше 9, тому що в кожному квадраті на рисунку не може бути двох точок, бо інакше була б пара точок що має відстань меншу за $r$. А тому максимум може бути 9 точок.

Отже нам необхідно шукати точки в прямокутнику, вміти додавати і видаляти точки. Це можна робити використавши дерево відрізків, де в кожній вершині дерева відрізків будемо підтримувати множину точок, впорядковану за $y$, для усіх точок в яких $x$ покритий проміжком вершини. При операції додавання або видалення нам необхідно оновити значення в $O(log)$ вершин, а в одній вершині оновлювати множину можемо за $O(log)$. Тому складність для однієї операції буде $O(log^2)$.

Код розв’язку C++

A. Шахова дошка

Зауважимо, що в межах чорних та білих діагоналей елементи можна рухати та переставляти довільним чином за 0 хвилин. Отже, кожна клітинка яка на початку розташована не на своїх діагоналях має бути переставлена на свої обміном за 1 хвилину. Оскільки за один хід ми переставляємо дві такі клітинки, то відповідь — це кількість клітинок, які початково не на своєму місці, поділена на два.

B. Загублений рядок

Єдині випадки, коли такого рядка не існує:

У послідовності є два значення 1, 3 або 3, 1 підряд. Тоді 2 символи на перетині повинні бути одночасно однаковими та різними, що неможливо.
У послідовності є три значення 3, 2, 3 підряд. Тоді перші 3 символи повинні бути однаковими, 4 символ повинен відрізнятись від них, а потім знову 3, 4 і 5 символ повинні бути однаковими, що неможливо.

Для решти послідовностей відповідний рядок завжди існує.

C. Нова розвага

Подвоїмо масив $a$. Для кожної початкової позиції $i$ знайдемо значення $L_i$ — найлівіший можливий індекс, де закінчується входження перестановки $p$ як підпослідовності, якщо починаємо розглядати масив $a$ починаючи з індексу $i$. Маючи ці значення, можна для кожного циклічного зсуву перевірити чи він підходить.

Щоб порахувати $L_i$ достатньо обчислити наступну динаміку: $DP_i$ — найлівіший індекс, де закінчується входження перестановки $p$, якщо ми зараз знаходимося в $i$-у елементі масиву $a$ (і, відповідно, в $j$-у елементі перестановки $p$, такому що $p_j = a_i$, такий індекс є унікальний). Таку динаміку легко обчислити, якщо знайти значення $Next_i$ — де в масиві знаходиться найближчий елемент, який є наступним в перестановці $p$, після $a_i$. Всі значення можна обчислити зі складністю $O(n)$.

D. Позитив

Розглянемо масиви часткових сум — $sa[i] = a[1] + a[2] + \dots a[i]$. Аналогічно масив $sb[i]$. Марічка може з’їсти перші $x$ цукерок з першого ряду і перші $y$ цукерок з другого ряду, якщо $sa[x]+sb[y] \ge 0$.

Припустимо, що в обох масивах часткових сум максимальне значення розташоване в кінці масиву.

Нехай Марічка з’їла $x$ цукерок з першого рядку і $y$ з другого. Скажемо, що якщо Марічка їсть цукерки з одного з рядів, то їй вигідно це робити поки значення у відповідному масиві часткових сум не стане більшим за попереднє. Тобто, якщо Марічка їсть з першого ряду, то їй вигідно це робити поки вона не дійде до такого $new_x$, що $sa[new_x] \ge sa[x]$. Якщо дівчина може таким чином з’їсти з першого ряду всі цукерки до $new_x$, то це точно вигідно, бо рівень задоволення Марічки стане більшим. Якщо ж Марічка не може цього зробити (рівень задоволення може стати від’ємним), то варто спробувати збільшити рівень задоволення за рахунок цукерок з другого ряду. Починати їсти з першого ряду тоді взагалі не вигідно, адже таким чином Марічка зменшить рівень задоволення, і можливо уже не зможе їсти з другого.

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

Якщо ж найбільші значення знаходяться не в кінці масиву, то даним алгоритмом Марічка може з’їсти усі цукерки до позицій, де знаходяться максимуми в обох масивах. Зауважимо, що далі можна розглядати усі значення з кінця і аналогічним алгоритмом розв’язати другу половину, адже позиції максимумів залишаться такими ж.

Складність такого розв’язку $O(n)$.

E. Розмалюй і володарюй

Поділимо всі вершини на 4 групи по $n \over 4$ вершини. В першу хвилину пофарбуємо в синій колір 1 і 2 групу вершин, у другу хвилину 1 і 3 групу, у третю хвилину 1 і 4 групу. Таким чином кожна пара вершин була пофарбована в один колір хоча б раз, а отже ми точно видалимо всі можливі ребра. Отже за 3 хвилини завжди можливо.

Тепер потрібно перевірити, чи можливо менше, ніж за 3 хвилини. Якщо у графі немає ребер, то відповідь 0. Це стається, коли у жодної пари чисел немає спільного одиничного біту.

Розглянемо певний біт, оберемо усі вершини, в яких цей біт рівний 1. Повинна існувати хвилина, в якому всі обрані вершини пофарбовані в один колір. Інакше за 2 хвилини не вийде видалити ребра між усіма парами обраних вершин.

Тоді за одну хвилину можна обрати 2 підмножини бітів (одну з них фарбуємо в синій колір, іншу в жовтий) так, щоб:

ці підмножини не перетиналися
для кожної з підмножин існувало не більше $n \over 2$ чисел, які мають хоча б 1 біт з підможини
не існувало жодного числа, яке має біти з обох підмножин

Можна перебрати усі пари підмножин та перевірити ці умови за $3^{18}$ операцій.

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

F. Довгі дерева

Нехай ми вибрали довільний підграф та пару вершин в ньому. Для всіх таких виборів подивимось, чи відстань між вибраною парою є не меншою за кількість листків. Якщо це так, то покращимо відповідь сумою ваг вибраних вершин. Неважко побачити, що це значення буде рівним відповіді на оригінальну задачу.

Підвісимо дерево за довільну вершину і зробимо динамічне програмування зі станом [корінь піддерева][відстань між двома вибраними вершинами мінус кількість листків у вибраному підграфі][параметр 0/1/2], де 0 — ще не почали прокладати шлях між двома вибраними вершинами, 1 — шлях проходить із довільної вершини в піддереві до його кореня, 2 — шлях повністю проходить в піддереві. Значенням цього стану є загальна вартість вибраних у підграф вершин.

Загальна складність $O(n^2)$, оскільки другий параметр стану (баланс) може приймати значення від $-c$ до $c$, де $c$ не більший за розмір піддерева.

G. Розділи цукерки

Розв’язок 1

Скажемо, що елемент $x$ лівий, якщо в першій перестановці його ліве входження, інакше правий. Тепер розглянемо 2 елементи $a$, $b$ ($a<b$) і їх відносне розташування:

$aabb$: немає обмежень
$bbaa$: відповідь 0
$abba$: $a$ — лівий
$baab$: $b$ — правий
$baba$: $a$ — лівий, $b$ — правий
$abab$: якщо $a$ правий, то $b$ теж правий; якщо $b$ лівий, то $a$ теж лівий

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

У кожному ланцюжку усі елементи на префіксі повинні бути лівими, а на суфіксі правими. Всі ці варіанти відрізняються, адже для них усіх відрізняється перша пара елементів, яка утворює інверсію, крім можливо варіанту, коли всі ліві чи всі праві. Такі 2 варіанти відрізняються, якщо існує якийсь уже відомий елемент, який попадає між елементами ланцюжка. Тобто відповідь потрібно домножити на $len+1$, якщо є ще якийсь елемент, та на $len$ якщо ні, де $len$ — довжина ланцюжка.

Наприклад для [1, 1, 2, 3, 2, 4, 3, 4] елементи 2, 3, 4 утворюють ланцюжок довжиною 3 і не існує жодного іншого елемента, який з ним перетинається, тому домножуємо відповідь на 3. А для [1, 2, 3, 2, 4, 1, 3, 4] елемент 1 — лівий, елементи 2, 3, 4 утворюють ланцюжок довжиною 3, але оскільки елемент 1 перетинається з ланцюжком, то відповідь домножається на 4.

Знаходити ланцюжки можливо за $O(n)$, якщо перебирати усі елементи від 1 до $n$.

Розв’язок 2

Позначимо як $a$ та $b$ позиції одиниці в заданій послідовності ($a < b$). Порахуємо відповідь динамічним програмування $R_a$ — кількість способів вибрати 2, 3, … $n$ (в такому порядку) після позиції $а$ так, щоб все решта (те що не взяли) правіше від $а$ було унікальним. Те саме порахуємо для позиції $b$ і додамо до відповіді.

Тепер потрібно відняти те, що порахували двічі. Щоб щось порахували двічі потрібно аби існував підрядок який починається в позиції $a$ і проходить через позицію $b$, який є мерджем двох впорядкованих послідовностей [$1, 2, …, k$]. В одному варіанті з нього взяли одну підпослідовність у відповідь, в іншому - іншу, тим сами генеруючи однакові підпослідовності. Тому знайдемо найкоротший такий підрядок і віднімемо від поточної відповіді відповідь на суфіксі після нього.

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))$.

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

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

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$. Тепер є два випадки:

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

Розв’язок за \(O(\sum_{i} a_i)\).

Розв’язок за \(O(n^2 \log n)\).

Розв’язок за \(O(n^2)\).