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. Ремонтні роботи

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

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

2. Між кожною парою сусідніх вибраних точок має бути хоча б одна компанія.

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

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

Код розв’язку 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++

Let \(d\) be the largest degree of a node in the tree. We will prove that the answer is \(n-1-d\).

First, we can immediately notice that if we make a move on outhouses \(x,y\) and \(z\), we will increase the degree of \(x\) by \(1\) and decrease the degree of \(y\) by \(1\). This means that we can increase the maximum degree in the tree by at most \(1\) in each move. Since a star has maximum degree \(n-1\), we need to make at least \(n-1-d\) moves.

Now we actually need to find a sequence of \(n-1-d\) moves. Let \(s\) be a vertex with degree \(d\). Suppose that the tree isn’t a star with center \(s\). Then there exists a path of length \(2\) starting at \(s\); say \(s-x-y\). Preforming a move on these vertices disconnects \(x\) and \(y\), and connects \(y\) to \(s\), increasing the degree of \(s\) by \(1\). So, as long as the tree isn’t a star, we can increase the degree of \(s\) by \(1\), and so we can preform \(n-1-d\) moves to get \(s\) to have degree \(n-1\).

We can either simulate the above algorithm, taking \(O(N)\) to find the move in each step (leading to total time complexity \(O(N^2)\)). Alternatively, one can easily notice that running a DFS algorithm from \(s\) and outputting \(s-x-y\) for every edge we encounter \(xy\) not incident to \(s\) in order will essentially do the same thing as the above paragraph describes in \(O(N)\) time (this can be proven by induction, say).

Let’s analyze when does array \([a_1, a_2, \ldots, a_n]\) satisfy the conditions of the problem.

1. If \(a_1+a_2+\ldots +a_n = 0\), then it’s a NO. Now, assume \(a_1+a_2+\ldots+a_n>0\) (otherwise just negate all elements).

2. If array contains at most one nonzero value, it’s a NO.

3. Let the sum of positive elements be \(P\), and the sum of negative elements be \(-N\), with \(P>N\). Denote \(S=P-N\). If we order all positive elements first, and then all negative, then all prefix sums will be positive, so we only have to worry about suffix sums. Alternately, we only need to order positive elements so that no prefix sum equals exactly \(S\).

4. If not all positive elements are equal, then it’s always possible to order positive elements in such a way, so it’s a YES. Indeed: assume there are some positive elements \(x\neq y\). First, as many other positive elements as you can so that no prefix sum is \(S\). If we could order all of them, then we put \(x, y\) in one order or another, making sure new prefix sum is also not \(S\). Otherwise, there are some elements remaining, but we can’t append any more without getting sum exactly \(S\), which means all remaining elements are equal to some \(t\). Then put \(x\) or \(y\) (whichever is \(\neq t\)), then \(t\), then all remaining positive elements: we successfully avoided \(S\).

5. Now assume all positive elements are equal to some \(x\). If \(S\) is not divisible by \(x\), we can still put all positive elements, and then all others, so in that case the answer is also YES. So now we assume that \(P, S, N\) are divisible by \(x\).

6. Assume some negative number \(y\) isn’t divisible by \(x\). Then let’s put \(y\) first, then all \(x\)s, then all remaining elements. Note that every prefix sum is either positive or not divisible by \(x\), and every suffix sum is also either negative or not divisible by \(x\), so the answer in this case is also YES.

7. Otherwise, all numbers are divisible by \(x\). So let’s divide everything by \(x\), and assume that \(x = 1\) from now on.

8. Let’s think about the prefix sums a bit more deeply. We want each prefix sum (except the first and last one) to be \(\neq 0, S\). They also start with \(0\), and end with \(S\). In addition, whenever prefix sums increase, they increase by exactly \(1\) (since that’s the only positive elements we have). So, if they ever get negative, in order to get to \(S\), they would have to cross \(0\) at some point.

9. So, the arranging process looks as follows. We start with \(0\), and then at every step we can either use \(1\), increasing sum by \(1\), or use some negative number \(-x\), decreasing sum by \(x\). We cannot ever get to \(0\) or \(S\) (except first or last position), so we have to always remain in the \([1, S-1]\) range. So, if there exists some negative number \(<-(S-2)\), the answer has to be NO.

10. It’s easy to see that otherwise such an arrangement always exists: just place \(1\)s until sum doesn’t exceed \(S-1\), and then use some negative number.

Now, we need to write \(dp\) for this. Once again, let’s break this down into small steps.

1. Total number of arrays is \((2m+1)^n\).

2. Calculate number of arrays \(\in [-m, m]^n\) with sum \(0\), you can do this in \(O(mn^2)\), subtract it.

3. Need to calculate only number of bad arrays with positive sum (then multiply it by \(2\) and subtract).

4. Iterate over positive element \(x\). We know all elements have to be divisible by \(x\), so we need to solve the instance with positive elements equal to \(1\), and all elements now being in \([-\frac{m}{x}, \frac{m}{x}]\).

5. Iterate over: number of ones \(P\), and sum of negative elements \(-N\) with \(N<P\). Then all negative elements have to be up to \(S-2=P-N-2\). So, we need to count the number of arrays of length \(n-P\) of nonnegative numbers with sum \(N\) with elements not exceeding \(P-N-2\).

6. We will use more general dp for this: \(dp[len][sum][lim]\): the number of arrays of length \(len\) with sum \(sum\) and all elements in \([0, lim]\). We can code this in \(O(MAXX^4)\), where \(MAXX = max(n, m)\). Indeed, transitions are simple: calculate values for \(lim\) from \(0\) to \(MAXX\), every time iterate how many values equal to \(lim\) you are adding.

Total runtime: \(max(m, n)^4\) with a very good constant (can actually be done faster but we reduced constraints enough).

Let \(X \subseteq V\). We denote by \(f(X)\) the number returned by the interactor. Let \(A, B \subseteq V\) be two sets of vertices such that \(A \cap B = \emptyset\). If \(f(A) + f(B) \neq f(A \cup B)\), there are two cases:

• \(\exists x \in A\) and \(y \in B\) such that \((x, y) \in E\).

• \(\exists z \in V\) such that \(z \notin (A \cup B)\) and \(\exists x \in A\) and \(\exists y \in B\) such that \((x, z)\), \((y, z) \in E\).

Both cases represent the fact that \(x\) and \(y\) are connected. In fact, that also means that \(dist(x, y) \le 2\) where \(dist\) is the distance between two vertices in the original graph.

Thus, we can start with \(A = \{1\}\) and \(B = \{2, 3, \dots, |V|\}\) and binary search the next vertex that can be added to \(A\) such that we know that all vertices of \(A\) are in the same connected component. Firstly, we can check that \(f(A) \ne 0\), the graph is not connected otherwise. At each step of the binary search we divide the set \(B\) into two sets \(B_1\), \(B_2\) such that \(B_1\) has the first \(\frac{|B|}{2}\) elements, and \(B_2\) the last \(|B| - \frac{|B|}{2}\). If \(f(A) + f(B_1) \neq f(A \cup B_1)\), then we continue the search for the vertex to add to \(A\) in \(B_1\), otherwise in \(B_2\). Then we know that the distance from the vertex we found to some vertex in \(A\) is at most 2 and that means they are in the same connected component, so we can add that vertex to \(A\). The number of queries used is at most \(2 \cdot |V| \log{|V|}\).

Puss in Boots in his turn can take candies from all piles, so he can take all candies. Puss in Boots can lose only if he cannot make \(n\) moves in his turn. This would happen if the total number of candies across all piles is less than \(n\). Therefore, the optimal strategy for Donkey is to take all the candies from the biggest pile. There is also the case where all piles start with 0 candies. In this case, neither player can make a move, and the game ends immediately, with Donkey’s defeat.

The key idea is to try to characterize all good placements of rooks. It turns out they all have to lie on a rhombus of some sort. Note that the condition on all Manhattan distances being at most \(n\) is equivalent to the following:

• There exist some integers \(A, B\), such that for every rook \((x, y)\) we have \[A\leq x-y \leq A+n\] \[B\leq x+y\leq B+n\]

Note that it follows that \(A+B \leq 2x = (x-y)+(x+y) \leq A+B+2n\) for any rook \((x, y)\), so \(\frac{A+B}{2} \leq x \leq \frac{A+B}{2}+n\). Since \(x\) can be any number, we get \[\frac{A+B}{2}\leq 1, \frac{A+B}{2}+n \geq n \implies 0 \leq \frac{A+B}{2} \leq 1 \implies 0 \leq A+B \leq 2\]

Similarly, we know that \((B-A)-n \leq 2y = (x+y)-(x-y) \leq (B-A)+n \implies \frac{B-A}{2} - \frac{n}{2} \leq y \leq \frac{B-A}{2}+\frac{n}{2}\) for any rook \((x, y)\). Once again, it follows that \[\frac{B-A}{2} - \frac{n}{2} \leq 1, \frac{B-A}{2}+\frac{n}{2} \geq n \implies \frac{n}{2} \leq \frac{B-A}{2} \leq \frac{n}{2} + 1 \implies n \leq B-A \leq n+2\]

Consider the case of odd \(n = 2k+1\) first. Then there are \(4\) cases: \((A, B) \in \{(-k-1, k+1), (-k, k+1), (-k-1, k+2), (-k, k+2)\}\). Each of these cases is basically defining some rhombus inside which every rook has to be; all of them are symmetric in the sense that they can be obtained by rotating the board by \(90^\circ\). So, we will count the number of configurations working for the case \((A, B) = (-k-1, k+1)\), and for other cases just rotate the board.

From \((A, B) = (-k-1, k+1)\) it follows that for rook \((n, y)\) we have

\[-k-1 \leq n - y \leq -k-1+n, k+1 \leq n+y \leq k+1+n \implies k+1 \leq y \leq k+1 \implies y = k+1\]

So, there definitely has to be a rook at \((n, k+1)\): at the middle of the bottom column. It’s not hard to deduce where other rooks have to be.

Now it’s not hard to fill where the remaining rooks will be. Consider, for example, columns \(1\) and \(n\). From current constraints, it’s easy to see that corresponding rooks in them have to be in rows \(k\) or \(k+1\). So, it’s either \(\{(k, 1), (k+1, n)\}\) or \(\{(k+1, 1), (k, n)\}\). Then we can look at columns \(2, n-1\), and deduce that it’s either \(\{(k-1, 2), (k+2, n-1)\}\) or \(\{(k+2, 2), (k-1, n-1)\}\), and so on: all other rooks are split into pairs, for each of which there are two placement choices. We can easily find the number of placements that satisfy already placed rooks.

However, we need to be careful to not double count any configurations. Fortunately, there are only \(4\) of them that satisfy two choices of \(A, B\): one where rooks are placed at \[\{(1, k+1), (2, k), (3, k-1), \ldots, (k+1, 1), (k+2, n), (k+3, n-1), \ldots, (n, k+1)\}\]

And \(4\) its rotations. So just subtract whichever of these placements satisfy already placed rooks.

Runtime \(O(n)\).

The analysis for the case of even \(n = 2k\) is similar. Once again, there are \(5\) cases for \((A, B)\):

\[\{(-k, k), (-k, k+2), (-k-1, k+1), (-k+1, k+1), (-k, k+1)\}\]

Here the first four are also rotations as each other, and the last one is a bit different.

The base configuration for the first \(4\) looks as follows: there are two rooks at cells \((1, k+1), (k+1, 1)\), and for \(2 \leq i \leq k\) there are two rooks at \(\{(i, k+2-i), (2k+2-i, k+i-2)\}\) or at \(\{(i, k+i-2), (2k+2-i, k+2-i)\}\). Once again, iterate over these \(4\) rotations.

\((-k, k+1)\) corresponds to the following:

For every \(1 \leq i \leq k\), there are two rooks at \(\{(i, k+1-i), (2k+1-i, k+i)\}\) or at \(\{(i, k-i), (2k+1-i, k+1-i)\}\).

Once again, we need to avoid double counting. In this case, configurations that might be double counted are of form:

\[\{(1, k), (2, k-1), (3, k-2), \ldots, (k, 1), (k+1, n), (k+2, n-1), \ldots, (n, k+1)\}\]

And their rotations.

Runtime \(O(n)\).

The condition on is equivalent to:

• Two bags \(X\) and \(Y\) are good if and only if \(max(X)>min(Y)\) and \(max(Y)>min(X)\).

We can create a segment \([min(X), max(X)]\) that characterize a bag. Two bags are good iff their corresponding segments intersect (have at least one common point).

1. It’s never optimal to leave more than 2 objects in a bag. That’s because to check all conditions, we only use at most 2 values: minimum and maximum in the bag. If some bag contains 3 values \(a < b < c\), we will never use \(b\) to check whether a pair of bags is good and therefore could be removed.

2. So all bags should contain either 1 or 2 object, and we want to maximize the number of bags with 1 object. For now, consider the case when all bags have at least 2 objects initially. Bags with one object don’t create any corner cases, it is just easier to explain the solution.

3. If a pair of bags isn’t good initially, it can’t become good after removing objects. It also means that if we leave 2 objects in a bag \(X\), it should the minimum and the maximum. We want the segment corresponding to bag \(X\) to intersect with some other segments, and there are no conditions that it can’t intersect with some other segments. That means it’s optimal to choose the segment as large as we can – \([min(X), max(X)]\).

4. Let’s call a bag promising if we can leave 1 object in this bag and 2 objects in all other bags. Let’s find whether the bag \(A\) is promising. How to find whether we can leave the value \(x \in A\) as the only remaining value?

5. We can’t leave \(x\) as the only remaining value if and only if there exist bag \(B\) such that \(min(A)<max(B)<x\) or there exist bag \(C\) such that \(x<min(C)<max(A)\). In such case, bag \(A\) and bag \(B\) or \(C\) were initially good but not good anymore. To implement this, we can sort all values \(min(X)\) for all bags \(X\), sort all values \(max(X)\) and use binary search to find whether a value in a given range exist. Note that we should check every value \(x \in A\), not only \(x=min(A)\) or \(x=max(A)\).

6. Now, let’s call a bag special if we leave 1 object in it. Obviously, each special bag should be promising. We know that the condition holds for each pair of two non-special bags. Also, the condition holds and for each pair of special and non-special bag by the definition of promising.

7. Any pair of special bags can’t be good initially. If we leave only one value \(a \in A\) and only one value \(b \in B\), \(a<b\) and \(a>b\) can’t hold simultaneously.

8. This means that we should choose the largest subsequence of promising bags, such that each pair of chosen bags is not good. If we denote each bag by its segment, we should find the largest subsequence of non-intersecting segment. Such problem is well-known and can be solved greedily: sort all segments by right end and choose a segment if it doesn’t intersect with the last chosen segment.

9. If we have bags that contain 1 element initially, those will be promising and then chosen, so no corner case required.

   The complexity of the solution is \(O(m \log n)\), where \(m\) is the total amount of objects.

In this problem, we need to determine the longest subsequence with the property that it can be divided into blocks of equal elements of length at least 2. The main observation is that such a subsequence can be divided into blocks of equal elements of length 2 or 3. Thus, we can solve the problem by dynamic programming. Let \(dp[i]\) be the length of the longest subsequence with the property mentioned above in the prefix \(s_1, s_2, \dots, s_i\). We start by initializing \(dp[0] = dp[1] = 0\). Then, \(dp[i]\) can be computed with the following recurrence:

\[dp[i] = max \begin{cases} dp[i - 1] \\ dp[i - x] + 1, x = max \{j \vert j \in \{1, 2, \dots, i - 1\} \text{ and } s[j] = s[i] \} \\ dp[i - x - 1] + 2, x = max \{j \vert j \in \{1, 2, \dots, i - 1\} \text{ and } s[j] = s[i] \} \end{cases}\]

To fill the array \(dp\) we need to iterate from \(1\) to \(n\) and keep the last occurrence of each element. This can be done with an unordered_map/ map resulting in an algorithm of complexity \(O(n) / O(n \log{n})\). The answer is \(dp[n]\).

Consider two adjacent columns, assume in sorted order they are \(a_1 \leq a_2 \leq \ldots \leq a_n\) and \(b_1 \leq b_2 \leq \ldots \leq b_n\). For any permutation \(p\), what’s the maximum number of indices \(i\) such that \(a_i>b_{p_i}\)? (Therefore making the corresponding row not sorted).

Let’s see how to check if we can get at least \(k\) such indices. It makes sense to pair \(k\) the largest elements of \(a\) with \(k\) smallest elements of \(b\). It’s also clear that we should be pairing them in increasing order: \((a_{n-k+1}, b_1), \ldots, (a_n, b_k)\). Then we can get \(k\) pairs iff \(a_{n-k + i} > b_i\) for all \(1\leq i \leq k\).

Now, we can find the largest number of such pairs we can form with binary search over \(k\). This would work in \(O(n\log{n})\). We will denote this value by \(f(a, b)\). Denote the columns as \(a_1, a_2, \ldots, a_m\). Clearly, we cannot make more than \(f(a_1, a_2) + f(a_2, a_3), \ldots, f(a_{m-1}, a_m)\) unsorted rows. So, if \(f(a_1, a_2) + f(a_2, a_3), \ldots, f(a_{m-1}, a_m) < n\), the answer is NO.

It turns out that if \(f(a_1, a_2) + f(a_2, a_3), \ldots, f(a_{m-1}, a_m) \geq n\), we can make all rows not sorted! Algorithm is very simple. Arrange elements of the \(1\)-st column arbitrarily. Then, for \(i = 2, \ldots, m\), do the following:

Assume there are \(x\) sorted rows remaining (for \(i = 2\) we have \(x = n\)). We assume \(x\) largest elements of \(a_{i-1}\) are in precisely those columns (we will see why later). Now, arrange the elements of \(a_i\) as follows:

1. Put \(min(x, f(a_{i-1}, a_i))\) smallest elements of column \(a_i\) next to \(min(x, f(a_{i-1}, a_i))\) largest elements of column \(a_{i-1}\), as discussed before, making those rows not sorted.

2. Put \(x - min(x, f(a_{i-1}, a_i))\) largest elements of column \(a_i\) in remaining sorted rows.

3. Put other elements arbitrarily.

This way, we will get \(min(n, f(a_1, a_2) + f(a_2, a_3), \ldots, f(a_{m-1}, a_m))\) unsorted rows.

Runtime: \(O(nm\log{n}))\).

We split into two cases, whether \(|s|\) is even or odd.

Case 1: \(|s|\) is even. Let’s look at each bit independently. If the bit is set in any element of \(s\), we know it will exist in the \(\text{OR}\). This bit will exist in the \(\text{AND}\) if it’s set in every element of \(S\), and since \(|s|\) is even, then it won’t be set in the \(\text{XOR}\). So every bit set in the \(\text{OR}\) is set in at most one of \(\text{AND, XOR}\), so \(\text{AND}(s)+\text{XOR}(s)\leq\text{OR}(s)\). The equality is attained only when each bit is set everywhere, nowhere or in an odd number of elements (these are three distinct cases).

Let’s fix a ternary mask of size \(14\) (being the log of \(\max a\)), containing \(0\),\(1\) and \(?\). This mask represents that we want to select some subsequence such that:

• if \(mask[i]=1\), then all elements of this subsequence have bit \(i\) set;

• if \(mask[i]=0\), then no elements of this subsequence have bit \(i\) set;

• if \(mask[i]=?\), then an odd number of elements of this subsequence have bit \(i\) set.

We also have to ensure that the set is of even size. Let \(B\) be the multiset of elements of \(a\) that follow the pattern made by the ternary mask. Now we just need to find the number of even subsets of \(B\) that such that their xor is equal to one on the \(?\) positions. If our mask has \(m\) positions with a \(?\), suppose we look at every element in \(B\) as a vector in \(\mathbb{F}_2^{m+1}\) with entries corresponding to entries of those elements in the \(?\) positions, and also one \(1\) at the end to keep track of parity. We need to find the number of subsets of these vectors summing to \((1,1,\ldots,1,1,0)\) (the ones at the first positions mean that the \(XOR\) is \(1\) on the \(?\) positions; the zero at the end means that there is an even number of elements). By linear algebra (for example, the Rank-Nullity Theorem) we know that the number of such subsets is either \(0\) or \(2^{|B|-d}\), where \(d\) is the dimension of the subspace generated by the elements of \(B\). The way we can check whether the answer is \(0\) we need to find the basis generated by set \(B\) (by Gaussian elimination), and simply check whether we can obtain it (by doing this we also find the value of \(d\)). Once we check whether we can get it, we add \(2^{|B|-d}\). If \(m=0\) we actually add \(2^{|B|-d}-1\) because we don’t want to count the empty set.

Now the question becomes how do we find the basis for each mask? Doing this naively can be done in \(O(n\cdot \max a_i\cdot15)\) or \(O(\max a_i^2\cdot 15)\), which are too slow. The trick is to iterate through all the masks, and find the new basis through old ones. Let’s look at one \(?\) of the mask. First we replace the \(?\) with a \(0\) then a \(1\), to get to new masks \(mask_0\) and \(mask_1\). Intuitively, it makes sense we can find the basis for mask when we know the bases for \(mask_0\) and \(mask_1\). It can be tempting to do this by appending a \(0\) to the beginning of every vector in the basis \(mask_0\) and a \(1\) to the beginning of every vector in the basis \(mask_1\) and finding the basis of this set. This however won’t give us a correct basis, since the \(1\) we appended at the beginning of the vectors for \(mask_1\) can become a \(0\) during Gaussian elimination. The trick is that we actually know what this bit should be for each vector in the basis for \(mask_1\), because we already know what happened to a bit appended to always be \(1\) in the Gaussian elimination for \(mask_1\): it’s the last bit we added to track parity! So actually, we append \(0\) to the beginning of every vector in the basis of \(mask_0\) and the last entry (parity entry) to the beginning of every vector in the basis of \(mask_1\), and merge them using Gaussian elimination.

Case 2: \(|s|\) is odd. This is in some sense the harder case, but we will use a lot of the same ideas. First to identify what the bits look like. Here it is more uncomfortable since if \(\text{AND}\) has some bit set, then so does \(\text{XOR}\). So for each bit set in \(\text{OR}\), it can be set zero, one or two times on the left side. Subtracting the right side of the equation from the left we get \(\sum \pm2^{i_k}=0\), where all \(i_k\) are distinct, which is possible only if the sum is empty (because binary representation is unique). So the only possible way is for each bit set in the \(\text{OR}\) to be set only in \(\text{XOR}\) i.e. each bit is either set nowhere or set in some odd number of elements but not all of them.

Now suppose we take a mask like last time, but now consisting only of \(0\) and \(?\). Let \(B\subset A\) the elements matching this pattern restricted to the \(?\) positions again. We need the number of subsets of odd subsets of \(B\) that xor to \((1,1,1\ldots,1,1)\) and no bit is contained in all of them. This second condition is impossible to model using linear algebra. Best we can do is find the total number of such subsets (appending by \(1\) again to ensure its parity) and try to take away the sets which contain bits that are set in every element.

The way we do this is the principle of inclusion-exclusion. Let’s again take our ternary masks like in the previous case. We find the number of sets that have all zeros and ones on those positions, and has an odd number of ones on all \(?\) positions. Then we add \((-1)^{\text{(\# of 1s)}}*2^{|B|-d}\) to the solution if we pass the check. Let’s see what happens to a set that doesn’t have any bit set to 1 everywhere. It’s counted just once, for the mask with only \(?\) and \(0\). If a set has exactly \(k\) bits which are 1 everywhere, then it’s counted \(2^k\) times, but since we alternate signs, we actually count it \(\sum(-1)^t\binom{k}{t}=0\) times. So we counted everything the correct amount of times.

We now may solve this case in parallel with the first case. Once we obtain the basis for some mask, we check whether we can get \((1,1,\ldots,1,0)\) and if needed we can add the adequate amount from the first case to the solution, and then check whether we can get \((1,1,\ldots,1,1)\) and if needed we add the amount from the second case. The complexity of this solution is \(O(3^k\cdot k^2)\) where \(k=\log_2\max a_i\) (more precisely \(O(n+\max a_i^{1.58}\log(\max a_i)^2)\)) with the only part actually having log squared being merging bases). However, when calculating how many operations we actually need (summing the number of \(?\) squared for each mask) we get about \(1.2\cdot 10^8\), which runs very quickly, especially that we use the xor operation in the Gaussian elimination for merging bases. The rest of the solution works in \(O(3^k\cdot k)\).

Suppose we want to equalize the preferred temperature of all the swamp creatures to a target temperature \(x\) (the initial temperature of some of the creatures).

Let \(cnt\) be the number of creatures whose preferred temperature is different from \(x\). To change all creatures’ temperatures to \(x\), we need at least \(cnt\) evenings. This is because, in one evening, we can change the temperature of at most one creature to \(x\). Thus, each creature with a different temperature requires its own evening to change.

If there are at least two neighboring creatures with the target temperature \(x\), we can use them to propagate \(x\) further. Specifically, for any neighbor of these two creatures, we can change their temperature to \(x\) in one evening. Using this, we can iterate clockwise around the circle:

• If a creature already has temperature \(x\), we skip it.

• If a creature has a different temperature, we spend one evening changing it to \(x\).

Initially, there might not be two neighbors with the temperature \(x\). However, if we can find any group of three consecutive creatures where one creature’s temperature can be changed to \(x\), we can create two neighbors with \(x\). After that, the propagation process is the same as mentioned above.

If there is no triplet where a creature’s temperature can be changed to \(x\), it means we need at least \(cnt + 1\) evenings to change all temperatures to \(x\). This extra evening is required to create a group of three consecutive creatures where one creature’s temperature can be changed to \(x\). Suppose we have a triplet of consecutive creatures with temperatures \(x, y, z\), where (without loss of generality) \(y \le x \le z\). In this case, we can change \(z\) to \(y\). After this operation, we change \(y\) to \(x\), creating two consecutive creatures with the target temperature \(x\), enabling the propagation process to continue as before.

Thus, to solve the problem, we only need to determine if at least one group of three consecutive creatures where one creature’s temperature can be changed to \(x\). This determines whether the answer is \(cnt\) or \(cnt + 1\).

Runtime: \(O(n)\).

Let a group be a sequence of identical characters that appear consecutively. Let’s \(g_i\) be the size of \(i\)-th group. The relative order of such groups does not change, only their sizes.

To process a query of the first type, we need to find the first and the last group that will be changed by it. That process will be the same as a query of the second type. The first type of queries covers some groups entirely and at most two groups partially. Groups which are covered entirely will double in size. The group at both ends will increase in size by the number of their elements that are in range of a query. These modifications can be done with segment tree.

The second type of query has to find the smallest index \(j\) such that \(\sum_{i = 0}^j g_i \ge x\). It can be done with binary search or descent on Segment tree.

This problem can also be solved with Fenwick tree, as each group cannot double in size more than \(O(\log A)\) times. This means that we can modify each group size naively.

Complexity: \(O(n \log n)\) with descent and Segment tree or \(O(n \log n \log A)\) with Fenwick tree.

We denote a move by \((i, j), i \neq j\). If we perform the same move \(k\) times, we note it by \((i, j)^k\). Let \(pos_t\) represent the position at which we can find \(t\) in the permutation. We assume that we update \(pos\) after every move that we do.
Property 1: An optimal sequence of moves never contains \((i, j > i)\). A sequence of moves that achieves the same result, while only utilizing the \((i, j < i)\) kind of moves is \((j, 1)^{j-i}\), \((j-1, 1)^{i-1}\), but it only requires a cost of \(j-1 < j\).
Property 2: \((i, j < i)\) can be replaced by a sequence of moves of the same cost of type \((i, 1)\): \((i, 1), (j, 1)^{j-1}\).
Following the first two properties, there must exist an optimal sequence of moves only of the type \((i, 1)\).
Property 3: Let \(0 \leq t < n\) s.t. \(pos_t \nless pos_{t+1} < \ldots < pos_n\). If \(t = 0\), the permutation is already sorted. Since \(pos_t \nless pos_{t+1}\), the solution must contain at some time the move \((pos_t, 1)\).
Property 4: If the sequence contains a move \((pos_t, 1)\), then it must later contain \((pos_{t-1}, 1),\) \((pos_{t-2}, 1), \ldots(pos_{1}, 1)\) as well, because after \((pos_t, 1)\) \(t\) will be in front of \(1, 2, \ldots t-1\).
Property 5: If the sequence contains a move \((pos_t, 1)\), then the sequence mustn’t later contain \((pos_{z>t}, 1)\), since \(t\) and \(z\) will be correctly ordered, and we can’t break the correct ordering by doing any other moves required by property 4.
Using properties 3 and 4, the optimal sequence’s length must be at least \(t\), containing \((pos_t, 1),\) \((pos_{t-1}, 1), \ldots (pos_1, 1)\). Using property 5, we shouldn’t use any other moves. There is a sequence of moves whose length is exactly \(t\): \((pos_t, 1), (pos_{t-1}, 1), \ldots (pos_1, 1)\) (using properties 4 and 5, we won’t need to redo any moves if we employ this order).

We now have to figure out how to efficiently update \(pos\).
Property 6: When we have to do \((pos_{1 \leq z \leq t}, 1)\), \(pos_z\) will be higher than its original value by the number of values \(z < y \leq t\) that were originally to the right of \(z\). We move them to the first position earlier, therefore each increasing \(z\)’s position by one.
We need a data structure that supports point updates (i.e. we moved a value from index \(i\) to the first position) and range sum queries (how many values that were originally after us were moved before us to the front). A Binary Indexed Tree is enough for this.
Although we can sort the permutation with a cost of \(O(n)\), it’s not easy to find a solution that generates the required moves faster than \(O(n \log n)\).

Let’s make a binary search to find the answer. Now we need to check whether we can add weights such that the diameter is \(\le x\).

Let’s call the middle point of the diameter \(C\). It means that the distance from point \(C\) to any vertex is at most \(x/2\). And the existence of such point also means that diameter is \(\le x\) – the distance between vertices \(a\) and \(b\) \(dist(a, b) \le dist(a, C) + dist(b, C) \le x/2 + x/2 = x\).

The point \(C\) should lie on an edge (considering vertices also lie on an edge). Let’s iterate an edge \((a, b)\) where the point \(C\) lies. Let \(len\) be the original length of this edge.

Property: We should only add weights to edges which connect edges to their corresponding parents. If we add some positive amount to an edge not connecting a leaf, we can add the same value to all edges connecting leaves in the subtree instead.

Now let’s find whether the point \(C\) can lie on an edge \((a, b)\). Let’s call \(mx_a\) – maximum distance from vertex \(a\) to a leaf not using edge \((a, b)\). Same for \(mx_b\). Firstly, \(mx_a+len+mx_b\) should hold.

Let \(0 \le y \le len\) be a distance from point \(a\) to \(C\). If \(x\) is even, \(y\) should be integer. Otherwise, \(y\) is integer + 0.5 (we can multiply all distances by 2, then we have a condition whether \(y\) is even or odd).

The original distance from any leaf to \(C\) can’t be more than \(x/2\), so \(mx_a+y \le x/2\) and \(mx_b + len - y \le x / 2\), so \(y \in [max(0, mx_b + len - x/2), min(len, x/2 - mx_a)]\). If there is no possible solution, the edge \((a, b)\) doesn’t work.

Now let’s count how much weight we can add for a fixed \(y\) and compare it with \(w\). Let \(da_1, da_2, \dots, da_k\) be the distances from \(a\) to all leaves not using edge \((a, b)\). Same for \(db_1, db_2, \dots, db_m\). We can add \(\sum_{i=1}^k (x/2-y-da_i) + \sum_{i=1}^m (x/2 - (len-y) - db_i)\) = \((x/2-y)\cdot k + (x/2-(len-y))\cdot m - \sum_{i=1}^k da_i - \sum_{i=1}^m db_i\). It’s clear that the function is linear on \(y\) so we can try minimal and maximal possible values of \(y\).

Now, how to compute all of this fast. It’s enough to compute values \(mx_a\), \(cnt_a\), \(sum_a\), \(mx_b\), \(cnt_b\), \(sum_b\) for each edge.

Let \(cnt_a\) be the number of leaves reachable from \(a\) not using edge \((a, b)\).

Let \(sum_a\) be the sum of distances from \(a\) to all leaves not using edge \((a, b)\).

Then the formula become \((x/2-y)\cdot cnt_a + (x/2-(len-y))\cdot cnt_b - sum_a - sum_b\).

Now we only need to find all of those values for each edge. This is quite standard tree problem. We can compute all of those values for one edge and then recompute how the values change when we want to compute them for incident edges. This can be implemented in \(O(n)\).

The complexity of the whole solution is \(O(n \cdot \log maxAnswer)\).