Порахуємо остачу від числа \((-\sum_{i=1}^{k} a_i)\) за модулем \(p\). Якщо вона не перевищує \(m \cdot (n - k)\), то потрібну суму можна добрати за рахунок решти підходів, інакше — ні.
Розв’язком можуть бути два циклічні зсуви:
де елемент 1 стоїть на початку масиву,
де елемент 1 стоїть у кінці масиву.
Позначимо \(dp_i\) — максимальну кількість «щасливих» днів, якщо враховано лише перші i піц.
Щоб оновити \(dp_i\), потрібно визначити, скільки піц можна з’їсти в останній день. Нехай останній день охоплює підпослідовність \((j + 1, \dots, i)\). Вона має бути «щасливою», тобто жоден тип піци не зустрічається рівно один раз. Тоді \(dp_i = \max (dp_i, dp_j + 1)\).
Щоб швидко перевіряти, чи підпослідовність \((j + 1, \dots, i)\) є «щасливою», підтримуємо для кожного типу піци позиції її появ. Для кожного типу \(x\) між двома останніми появами збільшимо лічильник «поганих» позицій \(cnt_j\) на 1 — це означає, що в цьому діапазоні тип \(x\) зустрічається рівно один раз.
Таким чином, серед усіх позицій \(j\), де \(xnt_j = 0\) (тобто підпослідовність до \(i\) утворює щасливий день), обираємо ту, що дає найбільше \(dp_j\).
Для ефективної реалізації обчислення максимуму серед позицій із \(cnt_j = 0\) можна використовувати дерево відрізків або іншу структуру даних із можливістю оновлень \(cnt_j\) на відрізку і пошуку максимуму серед пар \((-cnt_j, dp_j)\).
Користуючись ознаками рівності трикутників, можна довести, що пара міток є збалансованою тоді і тільки тоді, коли ці мітки знаходяться на однаковій відстані від центру кола.
Якщо на відстані \(d\) від центру знаходяться \(k\) точок, вони можуть утворити \(\frac{k \cdot (k - 1)}{2}\) збалансованих пар. Тоді для вирішення задачі потрібно згрупувати точки за відстанню до центру кола і просумувати вищезазначену кількість для кожної відстані.
E. Бібоп, Рокстеді і операція Шреддера
Розглянемо операцію Шреддера для одного біта:
\(a_i = 0\), \(a_j = 0\) \(\rightarrow\) \(a_i = 0\), \(a_j = 0\),
\(a_i = 0\), \(a_j = 1\) \(\rightarrow\) \(a_i = 0\), \(a_j = 1\),
\(a_i = 1\), \(a_j = 0\) \(\rightarrow\) \(a_i = 0\), \(a_j = 1\),
\(a_i = 1\), \(a_j = 1\) \(\rightarrow\) \(a_i = 1\), \(a_j = 1\).
Тобто, якщо є рівно одна одиниця серед двох значень, то вона переміститься в \(a_j\). Отже, щоб максимізувати суму на відрізку \([l,r]\), потрібно перемістити туди якомога більше одиниць кожного біта. Якщо \(cny_i\) — кількість чисел із включеним \(i\)-им бітом у всьому масиві, то для відрізка відповідь рівна:
\[\sum_{i=0}^{19} \min(r - l + 1, cnt_i) \cdot 2^i\]
Розглянемо випадок, коли є лише два числа 0 та 1. Зауважимо, що є 2 випадки:
Коли немає двох підряд однакових елементів. Тоді на кожному кроці 0 заміниться на 1, а 1 на 0. Ми можемо легко визначити що де буде, через парність числа \(k\).
Коли є два підряд однакових елементи. Проміжки з однакових елементів будуть розширюватися на 1 в кожен бік, поки не зустрінуть інший такий проміжок. Відповідно для позиції ми можемо визначити що в ній буде, якщо знайдемо найближчий проміжок з двох однакових справа та зліва. Якщо \(k\) малень і жоден з проміжків не встигне розширитися, то ми можемо визначити що буде в цій позиції через парність \(k\) (як у першому випадку).
Тепер для розв’язання початкової задачі використаємо паралельні двійкові пошуки. Будемо йти від менших елементів до більших. Познчатимемо всі менші за поточне значення числа 0, а всі більші чи рівні 1. Таким чином ми звели задачу до запитів зміни 1 на 0 і знаходження, найближчих до певної позиції, двох однакових чисел підряд. Цю задачу можна розв’язувати за допомогою системи неперетинних множин. Для зручності числа можна стиснути.
Складність: \(O(n \log n)\).
Розглянемо випадок коли \(n \le m\), тоді \(n \le 10^6\).
Перебираємо \(i\) від \(-n\) до \(n\). Для кожного \(i\) двійковим пошуком знаходимо максимальне \(j\)(позначимо \(mx\)), що задовольняє \[\frac{i^2}{n^2} + \frac{j^2}{m^2} \le 1\].
До відповіді додамо \(2 \cdot mx + 1\).
Погані пари — це інверсії у перестановці. Позначимо їх кількість \(x\) Щоб зробити число інверсій кратним 4, достатньо виконати \(\min (x \mod 4, 4 - (x \mod 4))\).
Відповідь рівна \(m\).
Розв’яжемо задачу у зворотному порядку — додаватимемо вправи до програми. Нехай \(dp_i\) — довжина максимальної послідовності вправ, що задовольняє умови, якщо \(i\)-та вправа виконується останньою.
Для кожної довжини \(x\) зберігатимемо у \(pos_x\) всі позиції \(j\), де \(dp_j = x\).
Коли додаємо вправу \(i\):
Знаходимо \(dp_i\), перебираючи \(x\) від \(1\) до \(a_i - 1\). У \(pos_x\) шукаємо найправішу позицію \(j < i\), де \(dp_j = x\). Перевірим, чи \(a_j < a_i\), якщо це так, то оновимо \(dp_i = \max(dp_i, x + 1)\).
Після цього оновлюємо вправи, для яких \(i\)-та може бути передостанньою. Будемо пробувати шукати позиції \(k\) які треба оновити. Серед позицій \(k\), де \(dp_k = dp_i\), знайдемо найлівішу для якої виконується \(i < k\). Якщо виконується \(a_i < a_k\), то оновимо значення \(dp_k\) і продовжимо шукати позиції \(k\). Після цього рекурсивно повторюємо процес для наступних вправ \(k\).
K. Подільність в дивній системі
Оскільки \(x^i \mod (x - 1) = 1\), маємо: \[(\sum n_i \cdot x^i) \mod (x - 1) = \sum n_i \mod (x - 1)\]
Отже, щоб перевірити, чи \(n\) ділиться на \(m - 1\), достатньо перевірити, чи сума його цифр у системі з основою \(m\) ділиться на \(m - 1\).
Припустимо, що ширина більша, ніж висота. Побудуємо одну захисну лінію, рухаючись вправо, поки це можливо, потім піднімемось угору на один крок і повторюватимемо це.
Позначимо точки, де відстань до лівого краю дорівнює відстані до нижнього краю. Між такими точками можна змінити горизонтальні та вертикальні лінії без порушення умов. Отже, кількість можливих ліній дорівнює \(2^k\), де \(k\) — кількість таких проміжків.
Розглянемо задачу на смужці \(3 \times
m\). Для кожного стовпця можна за одну операцію пофарбувати всі
клітинки відповідно до потрібного візерунка, окрім шаблону
101. Для таких стовпців спочатку зафарбовуємо всі три
клітинки, потім пофарбуємо центральний рядок в 0. Таким чином, смужку
можна обробити за \(m + 1\) операцію,
що достатньо для розв’язання задачі.