Обласна олімпіада 2025 (розбір) | Статті

A. Дивна шеренга

Одноцифрові числа ($0$–$9$) завжди дивні, а багатоцифрові числа, що є паліндромами, містять повтори.

Якщо $n < 10$, тоді відповідь рівна $n+1$, інакше — $10$.

В. Алфавітна послідовність

Розділимо масив на зростаючі послідовності. Для цього перебираємо шеренгу: якщо $s[i+1] > s[i]$, продовжуємо послідовність, інакше — починаємо нову послідовність.

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

C. Гарна шеренга

Шеренга з $k$ коней є гарною, якщо її множина номерів рівна $\{1,2,\dots,k\}$. Тоді кількість таких шеренг дорівнює $k!$, а відповідь — $\displaystyle\sum_{k=1}^{n} k!$.

Зауважимо, що для $k > m$ маємо $k! \equiv 0 \pmod{m}$. Тому, якщо $n > m$ суму можна обчислити для $k=1,\dots,m$.

Відповіддю буде результат такої суми: $\displaystyle\sum_{k=1}^{\min(n,\,m)} k! \pmod{m}$.

D. Відгадай шеренгу

Нехай $s$ — зафіксована шеренга коней довжини $n$. Розгл’янемо всі можливі рядки з $n$ символів (від a до z) впорядковані лексикографічно від мінімального $L = \mathtt{a\ldots a}$ до максимального $R = \mathtt{z\ldots z}$.

За допомогою бінарного пошуку по цьому відрізку, використовуючи відповіді:

• $=$ — рядок вгадано,

• $<$ — наша спроба менша за $s$,

• $>$ — наша спроба більша за $s$,

можна знайти $s$ за $O(n \cdot \log 26)$ запитів, що гарантує не більше 1000 спроб.

Для розв’язку необхідно трактувати рядки як числа в системі числення з основою 26 і реалізувати операції додавання і ділення на 2 в стовпчик. Також можна скористатись вбудованою в Python, C# або Java довгою арифметикою, вибрати межі для двійкового пошуку: $L = 0, R = 26^n - 1$ і перед виводом переводити числа в систему числення з основою 26.

E. Мiшки з вiвсом

Розглянемо декілька важливих фактів для розв’язку:

• Для довільної групи коней з вагами $a_{i_1}, a_{i_2}, \dots, a_{i_k}$ мінімальна кількість ходів для приведення їх до одного значення дорівнює $\sum_{j=1}^{k} |a_{i_j} - x|$, де оптимальне $x$ — медіана цієї групи.

• Оптимальну групу з $k$ коней можна вибрати як підрядок відсортованого масиву. Тобто, після сортування масиву $a$ отримуємо $b_1 \le b_2 \le \dots \le b_n$.

Використавши ці факти можна зробити такий розв’язок:

1. Відсортувати масив $a$ за неспаданням: $b_1, b_2, \dots, b_n$.

2. За допомогою префіксних сум обчислимо суму елементів для швидкого підрахунку вартості перетворення.

3. Для кожного підрядка довжини $k$ (тобто для кожного $i$ від $1$ до $n-k+1$):

   • Нехай медіаною є $b_{m}$, де $m = i + \lfloor \frac{k-1}{2} \rfloor$ (для парного $k$ можна обрати будь-який із середніх).

   • Обчислити вартість перетворення: $$\text{cost} = \left( b_m \cdot (m-i) - (P_{m-1} - P_{i-1}) \right) + \left( (P_{i+k-1} - P_m) - b_m \cdot (i+k-m-1) \right),$$ де $P_j = \sum_{t=1}^{j} b_t$ — префіксна сума, а $P_0 = 0$.

4. Відповіддю буде мінімальна знайдена вартість серед усіх можливих підрядків.

F. Кінські команди

Розглянемо розв’язок для $n \le 2 \cdot 10^3$. Нехай $dp[i]$ — відповідь на задачі для масиву $a_1, \dots, a_{i}$, $dp[0] = 0$. Тепер ми можемо перебрати індекс найправішого видаленого числа $j$ та оновити $dp[i]$ значенням $dp[j - 1] + (a_{j + 1} \oplus a_{j + 2} \oplus\dots \oplus a_i)$. Таку динаміку можна порахувати за $O(n^2)$.

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

G. Зустрiч на iподромi

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

Нехай для кожної ділянки $u$ ми обчислили:

• $d(u)$ — мінімальну кількість ходів від $u$ до входу в цикл (тобто до першої вершини, що повторюється);

• $\mathit{id}(u)$ — ідентифікатор компоненти, до якої належить $u$;

• $p(u)$ — позицію вершини $u$ на циклі (якщо $u$ вже в циклі).

За умовою, кожен кінь може за одну хвилину або залишитися на місці, або пройти за своєю єдиною доріжкою. Тому, якщо кінь стартує з $u$, то він може потрапити у вершину $f^t(u)$ за $t$ ходів, а завдяки можливості чекати — залишатися в цій же вершині будь-який час після $t$.

Розглянемо запит із початковими ділянками $u$ та $v$ :

1. Якщо $\mathit{id}(u) \neq \mathit{id}(v)$, їхні шляхи не перетнуться, тому відповідь $-1$.

2. Якщо $f^{d(u)}(u) = f^{d(v)}(v)$ то зустріч відбудеться у деревовидній частині, а саме у найнижчому спільному предок вершин $u$ та $v$.

3. Якщо ж жодна з попередніх умов не виконується, то коні зустрінуться на циклі. Можна показати, що оптимальне місце зустрічі буде або у вершині $f^{d(u)}(u)$ або $f^{d(v)}(v)$.