Зауважимо, що в межах чорних та білих діагоналей елементи можна рухати та переставляти довільним чином за 0 хвилин. Отже, кожна клітинка яка на початку розташована не на своїх діагоналях має бути переставлена на свої обміном за 1 хвилину. Оскільки за один хід ми переставляємо дві такі клітинки, то відповідь — це кількість клітинок, які початково не на своєму місці, поділена на два.
Єдині випадки, коли такого рядка не існує:
У послідовності є два значення 1, 3 або 3, 1 підряд. Тоді 2 символи на перетині повинні бути одночасно однаковими та різними, що неможливо.
У послідовності є три значення 3, 2, 3 підряд. Тоді перші 3 символи повинні бути однаковими, 4 символ повинен відрізнятись від них, а потім знову 3, 4 і 5 символ повинні бути однаковими, що неможливо.
Для решти послідовностей відповідний рядок завжди існує.
Подвоїмо масив \(a\). Для кожної початкової позиції \(i\) знайдемо значення \(L_i\) — найлівіший можливий індекс, де закінчується входження перестановки \(p\) як підпослідовності, якщо починаємо розглядати масив \(a\) починаючи з індексу \(i\). Маючи ці значення, можна для кожного циклічного зсуву перевірити чи він підходить.
Щоб порахувати \(L_i\) достатньо обчислити наступну динаміку: \(DP_i\) — найлівіший індекс, де закінчується входження перестановки \(p\), якщо ми зараз знаходимося в \(i\)-у елементі масиву \(a\) (і, відповідно, в \(j\)-у елементі перестановки \(p\), такому що \(p_j = a_i\), такий індекс є унікальний). Таку динаміку легко обчислити, якщо знайти значення \(Next_i\) — де в масиві знаходиться найближчий елемент, який є наступним в перестановці \(p\), після \(a_i\). Всі значення можна обчислити зі складністю \(O(n)\).
Розглянемо масиви часткових сум — \(sa[i] = a[1] + a[2] + \dots a[i]\). Аналогічно масив \(sb[i]\). Марічка може з’їсти перші \(x\) цукерок з першого ряду і перші \(y\) цукерок з другого ряду, якщо \(sa[x]+sb[y] \ge 0\).
Припустимо, що в обох масивах часткових сум максимальне значення розташоване в кінці масиву.
Нехай Марічка з’їла \(x\) цукерок з першого рядку і \(y\) з другого. Скажемо, що якщо Марічка їсть цукерки з одного з рядів, то їй вигідно це робити поки значення у відповідному масиві часткових сум не стане більшим за попереднє. Тобто, якщо Марічка їсть з першого ряду, то їй вигідно це робити поки вона не дійде до такого \(new_x\), що \(sa[new_x] \ge sa[x]\). Якщо дівчина може таким чином з’їсти з першого ряду всі цукерки до \(new_x\), то це точно вигідно, бо рівень задоволення Марічки стане більшим. Якщо ж Марічка не може цього зробити (рівень задоволення може стати від’ємним), то варто спробувати збільшити рівень задоволення за рахунок цукерок з другого ряду. Починати їсти з першого ряду тоді взагалі не вигідно, адже таким чином Марічка зменшить рівень задоволення, і можливо уже не зможе їсти з другого.
Тобто ми можемо порахувати позиції, де збільшуються значення часткових сум, а також які мінімальні значення зустрічаються між цими позиціями. Після цього жадно обираємо один з варіантів.
Якщо ж найбільші значення знаходяться не в кінці масиву, то даним алгоритмом Марічка може з’їсти усі цукерки до позицій, де знаходяться максимуми в обох масивах. Зауважимо, що далі можна розглядати усі значення з кінця і аналогічним алгоритмом розв’язати другу половину, адже позиції максимумів залишаться такими ж.
Складність такого розв’язку \(O(n)\).
Поділимо всі вершини на 4 групи по \(n \over 4\) вершини. В першу хвилину пофарбуємо в синій колір 1 і 2 групу вершин, у другу хвилину 1 і 3 групу, у третю хвилину 1 і 4 групу. Таким чином кожна пара вершин була пофарбована в один колір хоча б раз, а отже ми точно видалимо всі можливі ребра. Отже за 3 хвилини завжди можливо.
Тепер потрібно перевірити, чи можливо менше, ніж за 3 хвилини. Якщо у графі немає ребер, то відповідь 0. Це стається, коли у жодної пари чисел немає спільного одиничного біту.
Розглянемо певний біт, оберемо усі вершини, в яких цей біт рівний 1. Повинна існувати хвилина, в якому всі обрані вершини пофарбовані в один колір. Інакше за 2 хвилини не вийде видалити ребра між усіма парами обраних вершин.
Тоді за одну хвилину можна обрати 2 підмножини бітів (одну з них фарбуємо в синій колір, іншу в жовтий) так, щоб:
ці підмножини не перетиналися
для кожної з підмножин існувало не більше \(n \over 2\) чисел, які мають хоча б 1 біт з підможини
не існувало жодного числа, яке має біти з обох підмножин
Можна перебрати усі пари підмножин та перевірити ці умови за \(3^{18}\) операцій.
Тепер знайдемо усі підмножини бітів, які можливо покрити за одну операцію — об’єднання двох підмножин різних кольорів. Якщо можливо покрити всі біти за одну операцію, то відповідь 1. Інакше подивимось чи існують такі 2 підмножини, що в об’єднанні дають усі біти. Якщо так, то відповідь 2.
Нехай ми вибрали довільний підграф та пару вершин в ньому. Для всіх таких виборів подивимось, чи відстань між вибраною парою є не меншою за кількість листків. Якщо це так, то покращимо відповідь сумою ваг вибраних вершин. Неважко побачити, що це значення буде рівним відповіді на оригінальну задачу.
Підвісимо дерево за довільну вершину і зробимо динамічне програмування зі станом [корінь піддерева][відстань між двома вибраними вершинами мінус кількість листків у вибраному підграфі][параметр 0/1/2], де 0 — ще не почали прокладати шлях між двома вибраними вершинами, 1 — шлях проходить із довільної вершини в піддереві до його кореня, 2 — шлях повністю проходить в піддереві. Значенням цього стану є загальна вартість вибраних у підграф вершин.
Загальна складність \(O(n^2)\), оскільки другий параметр стану (баланс) може приймати значення від \(-c\) до \(c\), де \(c\) не більший за розмір піддерева.
Розв’язок 1
Скажемо, що елемент \(x\) лівий, якщо в першій перестановці його ліве входження, інакше правий. Тепер розглянемо 2 елементи \(a\), \(b\) (\(a<b\)) і їх відносне розташування:
\(aabb\): немає обмежень
\(bbaa\): відповідь 0
\(abba\): \(a\) — лівий
\(baab\): \(b\) — правий
\(baba\): \(a\) — лівий, \(b\) — правий
\(abab\): якщо \(a\) правий, то \(b\) теж правий; якщо \(b\) лівий, то \(a\) теж лівий
Нехай ми знайшли значення усіх елементів, які визначаються однозначно використовуючи дані обмеження. Подивимось на всі елементи, для яких ми ще не знаємо позицію. Можуть залишитись ланцюжки, де кожна пара сусідніх елементів перетинаються типом \(abab\). Розмежовані такі ланцюжки можуть бути елементами типу \(aabb\).
У кожному ланцюжку усі елементи на префіксі повинні бути лівими, а на суфіксі правими. Всі ці варіанти відрізняються, адже для них усіх відрізняється перша пара елементів, яка утворює інверсію, крім можливо варіанту, коли всі ліві чи всі праві. Такі 2 варіанти відрізняються, якщо існує якийсь уже відомий елемент, який попадає між елементами ланцюжка. Тобто відповідь потрібно домножити на \(len+1\), якщо є ще якийсь елемент, та на \(len\) якщо ні, де \(len\) — довжина ланцюжка.
Наприклад для [1, 1, 2, 3, 2, 4, 3, 4] елементи 2, 3, 4 утворюють ланцюжок довжиною 3 і не існує жодного іншого елемента, який з ним перетинається, тому домножуємо відповідь на 3. А для [1, 2, 3, 2, 4, 1, 3, 4] елемент 1 — лівий, елементи 2, 3, 4 утворюють ланцюжок довжиною 3, але оскільки елемент 1 перетинається з ланцюжком, то відповідь домножається на 4.
Знаходити ланцюжки можливо за \(O(n)\), якщо перебирати усі елементи від 1 до \(n\).
Розв’язок 2
Позначимо як \(a\) та \(b\) позиції одиниці в заданій послідовності (\(a < b\)). Порахуємо відповідь динамічним програмування \(R_a\) — кількість способів вибрати 2, 3, … \(n\) (в такому порядку) після позиції \(а\) так, щоб все решта (те що не взяли) правіше від \(а\) було унікальним. Те саме порахуємо для позиції \(b\) і додамо до відповіді.
Тепер потрібно відняти те, що порахували двічі. Щоб щось порахували двічі потрібно аби існував підрядок який починається в позиції \(a\) і проходить через позицію \(b\), який є мерджем двох впорядкованих послідовностей [\(1, 2, …, k\)]. В одному варіанті з нього взяли одну підпослідовність у відповідь, в іншому - іншу, тим сами генеруючи однакові підпослідовності. Тому знайдемо найкоротший такий підрядок і віднімемо від поточної відповіді відповідь на суфіксі після нього.