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

A. Жеребець і кобила

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

B. Квадратне пасовище

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

У випадку коли $n$ є непарним, то достатньо перевірити чи можна розташувати деяких коней, щоб покрити перший рядок і перший стовпець. Якщо вийде, то ми просто перейдемо до квадрата зі стороною $(n - 1)$, який є парним і ми в нього завжди зможемо розташувати коней. Оскільки ми можемо розташовувати лише лошат і кобил в перший рядок і стовпець, то нам цікаво чи в нас є достатньо цих коней, щоб покрити повністю ці ділянки: $a + 2b \ge 2n - 1$.

С. Гніді та вороні коні

Задачу можна переформулювати у таких термінах: ми залишаємо лише підрядок від $l$-го до $r$-го символу, за одну операцію можна видалити підрядок який має перший і останній символ однакові та має хоча б два символи та потрібно відповісти чи можна такими операціями видалити заданий підрядок.

У випадку коли $l = r$ зрозуміло, що ми не можемо виконати жодної операції тому відповідь No. Якщо ж $s[l] = s[r]$ тоді ми за одну операцію можемо видалити весь цей підрядок.

Для випадку коли $s[l] \neq s[r]$ достатньо перевірити чи існує така позиція $l < i < r - 1$ така що $s[l] = s[i]$ та $s[i + 1] = s[r]$ у такому випадку ми можемо видалити весь цей підрядок за дві операції, якщо ж такої позиції немає, то ми не зможемо видалити цей підрядок.

D. Доставка вівса

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

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

E. Деревоподібне пасовище

Розглянемо певний шлях ($a_1$, $a_2$, $\dots$, $a_k$) і нехай кількість сусідів для вершин на цьому шляху рівна $sz_1$, $sz_2$, $\dots$, $sz_k$ відповідно. Тоді такий шлях розділить дерево на $1 + (\sum_{i = 1}^{k} sz_i) - 2(k - 1)$, так початково була одна компонента і кожне ребро з вершиною шляху збільшить кількість компонент на 1, окрім ребер ті що є на шляху - таких $k - 1$ і ми їх врахували двічі. Цю формулу можна перетворити на таку $3 + \sum_{i = 1}^{k} (sz_i - 2) = 3 + \sum_{i = 1}^{k} val_{a_i}$, де $val_{v}$ рівне кількості сусідів вершини $v$ мінус 2.

В термінах задачі нам потрібно максимізувати суму значень $val_v$ на шляху починаючи з вершини $w$ і додати 3 до цього значення. Знайдемо максимальний по сумі значень шлях у дереві $A - B$, подібно до алгоритму пошуку діаметра в дереві. Можна довести що максимальний шлях з вершини $w$ буде завершуватись у одній з вершин $A$ або $B$. Тому порахуємо сумарне значення на шляху з вершини $A$ і вершини $B$, відповідь буде максимальне значення з цих двох шляхів плюс 3.

F. Найменше щасливе кратне

Побудуємо граф із $n$ вершин, де вершина відповідає за остачу по модулю $n$. З вершини $x$ будемо мати два переходи у вершини $(10x + 4)\%n$ та $(10x + 7)\%n$ - це буде означати що до побудованого числа з остачою $x$ ми можемо доставити цифру в кінець і отримати числа з такими остачами. У такому графі нас цікавить в першу чергу найкоротший цикл з вершини що відповідає за остачу 0 і серед таких найкоротших циклів нас цікавить лексикографічно найменший. Для того аби отримати потрібний результат будемо виконувати пошук вшир, де першочергово будемо розглядати перехід з додаванням 4 і після цього з додаванням 7.

G. Щасливе спільне кратне

Розглянемо конструкцію де певне число $val$ довжини $len$ повторюємо певну кількість разів $x$ так аби воно ділилось на $n$. Розглянемо значення цього числа $\frac{val \cdot (10^{len \cdot x} - 1)}{(10^{len} - 1)}$, це число має ділитись на $n$, тобто $val \cdot (10^{len \cdot x} - 1)$ має ділитись на $n \cdot (10^{len} - 1) = m$.

Використаємо теорему Ейлера: для взаємнопростих $a$ та $m$ виконується $a^{\varphi(m)} \equiv 1 \pmod m$. Розглянемо такі $n$ які взаємнопрості з 10, також використовуючи те що $10^{len} - 1$ взаємнопросте з 10, отримаємо $10^{len \cdot \varphi(m)} - 1 \equiv 0 \pmod m$. Якщо ми число $val$ повторимо $x \cdot \varphi(n(10^{len}-1))$ разів то таке утворене число буде ділитись на $n$, проте це правильно лише для $n$ взаємнопростих з 10.

Розглянемо що відбувається коли $n$ не є взаємнопростим із 10. Якщо $n$ ділиться на 5 то у такому випадку не існує ніякого щасливого числа, яке ділиться на 5.

У іншому випадку $n$ ділиться на 2, це означає що нам необхідно задовольнити аби щасливе число ділилось на певний степінь двійки. Для вирішення цього візьмемо $val = 447444474444447744$ - щасливе число яке ділиться на $2^{18}$, а отже ділиться і на усі можливі степені які може містити число $n$.

Можна показати що $(10^{18} - 1) \cdot \varphi(10^{18} - 1) \cdot \varphi(n)$ ділиться на $\phi(n(10^{18} - 1))$. Отже, нам достатньо рядок $447444474444447744$ повторити $(10^{18} - 1) \cdot \varphi(10^{18} - 1) \cdot \prod \varphi(n_i)$. Використовуючи правила ми можемо множити кількість повторів без жодних проблем.