Одноцифрові числа (\(0\)–\(9\)) завжди дивні, а багатоцифрові числа, що є паліндромами, містять повтори.
Якщо \(n < 10\), тоді відповідь рівна \(n+1\), інакше — \(10\).
Розділимо масив на зростаючі послідовності. Для цього перебираємо шеренгу: якщо \(s[i+1] > s[i]\), продовжуємо послідовність, інакше — починаємо нову послідовність.
Відповідь на задачу рівна максимальній довжині з усіх утворених послідовностей.
Шеренга з \(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}\).
Нехай \(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.
Розглянемо декілька важливих фактів для розв’язку:
Для довільної групи коней з вагами \(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\).
Використавши ці факти можна зробити такий розв’язок:
Відсортувати масив \(a\) за неспаданням: \(b_1, b_2, \dots, b_n\).
За допомогою префіксних сум обчислимо суму елементів для швидкого підрахунку вартості перетворення.
Для кожного підрядка довжини \(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\).
Відповіддю буде мінімальна знайдена вартість серед усіх можливих підрядків.
Розглянемо розв’язок для \(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 варіантів який елемент буде найправішим видаленим .
Оскільки з кожної ділянки виходить рівно одна доріжка, отримуємо функціональний граф. Кожна компонента такого графа складається з циклу, до якого «притікають» вершини, що знаходяться поза циклом.
Нехай для кожної ділянки \(u\) ми обчислили:
\(d(u)\) — мінімальну кількість ходів від \(u\) до входу в цикл (тобто до першої вершини, що повторюється);
\(\mathit{id}(u)\) — ідентифікатор компоненти, до якої належить \(u\);
\(p(u)\) — позицію вершини \(u\) на циклі (якщо \(u\) вже в циклі).
За умовою, кожен кінь може за одну хвилину або залишитися на місці, або пройти за своєю єдиною доріжкою. Тому, якщо кінь стартує з \(u\), то він може потрапити у вершину \(f^t(u)\) за \(t\) ходів, а завдяки можливості чекати — залишатися в цій же вершині будь-який час після \(t\).
Розглянемо запит із початковими ділянками \(u\) та \(v\) :
Якщо \(\mathit{id}(u) \neq \mathit{id}(v)\), їхні шляхи не перетнуться, тому відповідь \(-1\).
Якщо \(f^{d(u)}(u) = f^{d(v)}(v)\) то зустріч відбудеться у деревовидній частині, а саме у найнижчому спільному предок вершин \(u\) та \(v\).
Якщо ж жодна з попередніх умов не виконується, то коні зустрінуться на циклі. Можна показати, що оптимальне місце зустрічі буде або у вершині \(f^{d(u)}(u)\) або \(f^{d(v)}(v)\).