В цій задачі потрібно було просто перевірити чи для всіх \(i\) виконується \(|a_i - b_i| \le d\).
Очевидно, що перше число повинне бути непарне число, оскільки якщо ми
спочатку поставимо парне, то після першої ж транзакції банк заблокує наш
рахунок. Тепер, щоб сумарна парність наших покупок не змінювалася
(залишалася непарною) всі наступні числа повинні бути парними. Отже
відповідь YES є лише тоді, коли в нас рівно одне непарне
число.
Зауважимо, що в рядку, який зустрічється найбільшу кількість разів всі букви унікальні. Також, можна помітити, що найбільша кількість входження рядка, це найбільша з кількостей входження кожної букви. Розглянемо всі букви, що зустрічаються найбільшу кількість разів. Нехай, в нас є дві букви, що зустрічаються найчастіше \(a\) та \(b\) і після кожної букви \(a\) йде \(b\). Тоді рядок \(ab\) теж зустрічатиметься найбільшу кількість разів. Об’єднаємо всі такі пари в групи. Нехай \(sz\) — це розмір такої групи. Відповідь це \(\sum \frac{sz \cdot (sz + 1)}{2}\).
Складність: \(O(n)\).
Перший крок до розв’язання задачі — зрозуміти, що можемо спершу окремо розв’язати задачі для кожної компоненти зв’язності, а потім просто додати всі кількості.
Для простоти припустимо, що \(y = 0\), тобто аркуш складаємо лише горизонтально. Подивимось на якусь одну компоненту зв’язності в складеному аркуші. Можливі чотири випадки:
Жодна з коітинок компоненти не лежить в найправішому, або найлівішому стовпці аркуша. В такому випадку, у розкладеному варіанті аркуша, ця компонента повторюється рівно \(2^x\) разів: по одному разу в кожній копії аркуша. Зверніть увагу, що половина цих компонент буде віддзеркалена, але це не грає нам абсолютно ніякої ролі
Компонента містить хоча б одну клітинку в найлівішому стовпці аркуша, а також хоча б одну клітинку в найправішому стовпці аркуша. В такому випадку, у розкладеному варіанті аркуша, компонента стане одною великою компонентою, котра тягнеться від найлівішого стовпця аж до найправішого.
Компонента містить хоча б одну клітинку в найправішому стовпці аркуша, але не має жодної клітинки в найлівішому стовпці аркуша. В такому випадку, у розкладеному варіанті компонента об’єднається зі своїм дзеркальним відображенням праворуч, і таке об’єднання двох компонент буде повторюватися \(2^{x - 1}\) разів.
Компонента містить хоча б одну клітинку в найлівішому стовпці аркуша, але не має жодної клітинки в найправішому стовпці аркуша. В такому випадку, у розкладеному варіанті, найлівіша копія нашої компоненти не об’єднається ні з чим, але її перше дзеркальне відображення праворуч об’єднається зі своїм сусідом. Загалом вийде \(2^{x - 1} - 1\) таких об’єднаних компонент, де компонента об’єднана зі своїм дзеркальним відображенням ліворуч, а також одна найлівіша компонента без пари і одна найправіша компонента без пари. Всього \(2^{x - 1} + 1\) компонент.
Тепер зробимо наступне спостереження: можна такими ж міркуваннями знайти кількість компонент в розкладеному аркуші по вертикалі (тут треба буде дивитися чи має компонента клітинки в верхньому та нижньому рядках складеного аркуша), і просто перемножити кількості по горизонталі та вертикалі. Отриманий добуток і буде загальною кількістю компонент в розкладеному аркуші.
Відповідь на задачу — сума добутків по всіх компонентах.
Нехай \(f_{s_i, i}\) — відстань від символа \(s_i\) до наступного такого ж як він. Для кожного символа з алфавіту побудуємо розріджену таблицю, що шукає максимум. Коли приходить запит, то є 2 випадки: ми робимо стрибок, який строго всередині, або ні. Переберемо символ \(c\), по якому буде виконаний стрибок. Якщо стрибок строго всередині, то це зводиться до запиту в нашу таблицю. Якщо запит ззовні, то нам потрібно взяти останній символ \(c\), що був перед лівою межею запиту, або символ \(c\), що був після правої.
Складність: \(O(|s| \cdot (26 + \log{|s|}))\).
Початково посортуємо всі стовпці за зростанням, це не змінить відповіді. Використаємо підхід динамічного програмування. Нехай \(dp_{i, mask}\) — кількість способів розставити числа в перших \(i\) стовпцях, щоб числа з \(i\)-го стовпця та рядків, які належать \(mask\) закінчували неспадні рядки (інші можуть бути якими завгодно). Тепер потрібно перейти від стовпця \(i\) до стовпця \(i + 1\).
\[dp_{i + 1, mask2} = \sum_{mask1 = 1}^{2^n} dp_{i, mask1} \cdot f(i, i+1, mask1, mask2)\].
Тут \(f\) рахує кількість способів розставити спарувати числа з \(mask1\) та \(mask2\), щоб вони були неспадними. Щоб таке порахувати, будемо йти по бітах \(mask2\) від менших до більших. Оскільки числа ми посортували, то числа які ми розглядатимемо теж будуть йти в зростаючому порядку. Сунутимемо вказівник по \(mask1\), щоб знати зі скількома числами ми можемо спарувати поточне. Помноживо відповідь на цю кількість (потрібно пам’ятати, що деякі менші ми вже спарували з попередніми бітами). Після цього помножимо відповідь на \((b - popcount(mask))!\) оскільки всі інші ми можемо ставити в довільному порядку.
Після того визначимо масив \(ans\). \(ans_i = \sum_{i = popcount(mask)} dp_{i, mask}\). Потрібно відняти ті варіанти, які ми врахували декілька разів, тобто коли маска була підмаскої інших, довших.
Складність: \(O(4^n\cdot m \cdot n)\).
Для оптимального кодування символів з довжинами меншими ніж \(b\) використаємо Package-merge algorithm.
Щоб додати нижнє обмеження, зробимо лише \(b - a\) ітерацій даного алгоритму, та візьмемо \(n - 2^{a - 1}\) пакунок. Після цього до кожної довжини додамо \(a\).
Маючи всі довжини ми легко можемо побудувати префіксне дерево, йдучи знизу вверх, та відновити всі коди.
Складність: \(O(n \cdot (b + \log n))\).