Вам потрібно зчитати числа \(n, t\), а також n чисел \(a_{і}\). Тоді потрібно порахувати \(S = |a_0 - a_1| + |a_1 - a_2| + ... + |a_{n-2} - a_{n-1}|\). Відповідь буде \(t \cdot S\), її і виведемо.
Нехай в нас є деяка найкраща послідовність \(S_{ijk} = |a_i - b_j| + |a_{i+1} - b_{j+1}| + ... + |a_{i+k-1} - b_{j+k-1}|\) для певних \(i, j > 0\). Тоді зауважимо, що \(S^{\prime} = |a_{i-1} - b_{j-1}| + S_{ijk} \geq S_{ijk}\) також задовольняє умові і є не меншою ніж \(S_{ijk}\). Цей процес ми можемо повторювати доти доки одне з чисел \(i, j\) стане нулем. А отже існує найкраща послідовність де \(i=0\) або \(j=0\). Використаємо цей факт, щоб зробити два перебори. Перший по \(i\) де \(j=0\) (а також всеможливих \(k\)). Другий навпаки. Оберемо найкраще значення яке вдалось отримати. Складність \(O(N^2)\) де \(N\) довжина довшої з послідовностей.
Нормалізуємо всі вхідні рядки: будемо додавати в "нормалізованих" рядок символ за символом. Якщо два останні символи однакові — видаляємо їх. Складність такої нормалізації \(O(|s|)\). Після нормалізації рядок матиме один із двох видів: \(474747474....\) або \(747474....\).
Розглянемо що станеться, якщо з’єднати два такі рядки \(S_x\) і \(S_y\). Є два варіанти:
1. Якщо останній символ \(S_x\) та перший символ \(S_y\) різні, то стрічки просто з’єднаються: \(4747474...7+47474747...\). Довжина з’єднання дорівнюватиме сумі довжин \(S_x\) та \(S_y\).
2. Якщо останній символ \(S_x\) та перший символ \(S_y\) однакові, то після з’єднання вони знищаться. Наступні символи теж будуть однакові і знищаться. Це триватиме доки однин із рядків не стане порожнім.
\[4747474...4747+7474747... \rightarrow 4747474...474\textbf{77}474747... \rightarrow 4747474...47\textbf{44}74747... \rightarrow ...\]
Довжина з’єднання в цьому випадку дорівнюватиме абсолютній різниці довжин двох рядків.
Давайте окремо перевіримо, чи існує виграшна стратегія у першого гравця та чи існує виграшна стратегія у другого гравця. Якщо у жодного гравця немає виграшної стратегії, то гра завершиться нічиєю.
Спершу перевіримо, чи зможе перемогти другий гравець. Якщо він ходить вліво чи вправо, то перший гравець завжди може відмінити цей хід, якщо походить в протилежному напрямку. Отже, другий гравець в будь-якому разі буде вимушений ходити вгору. Значить, для першого гравця задача не програти, якщо він знає, що другий гравець завжди ходить вгору. Тобто перший гравець програє лише, якщо як би він не ходив, в результаті він попаде в стан, де більше не може робити хід. Аналогічно, він не програє, якщо заставить другого попасти в стан, де той не зможе походити вверх – найвища точка будь-якої вежі.
Тоді якщо першому достатньо бути на висоті \(х\) вежі \(k\), то йому також вигідно бути на висоті \(x-2\) цієї ж вежі або на висоті \(x-1\) вежі \(k-1\) або вежі \(k+1\).
Згенеруємо усі такі стани алгоритмом схожим на алгоритм Дейкстри. Для вежі \(k\) та парності \(c\), будемо знаходити такий найбільший \(2x+c\), що на такій висоті вигідно перебувати першому гравцю.
Далі, якщо ми хочемо знайти, чи зможе перемогти перший, то він змушений першим ходом ходити вгору. Далі задача залишається такою ж, адже гравці міняються ролями.
Спочатку згенеруємо всі щасливі числа з проміжку \([L, R]\). Загалом їх буде не більше, ніж \(T = 2^{19} - 2\), адже щасливих чисел довжини \(x\) є рівно \(2^x\).
Зафіксуємо число \(B\). Погрупуємо всі числа за остачами при діленні на \(2^B\) (значення останніх B бітів числа). Тепер цікаві пари можуть знаходитися в групах з остачами \(G_1, G_2\) лише якщо \(G_1 AND G_2 = 0\). Всього таких пар груп є \(O(3^B)\) адже для групи з остачею \(G\) підходять лише групи з підмасками числа \((2^B - 1 - G)\).
Позаяк щасливі числа мають досить випадкові двійкові представлення, можна побачити, що кількість чисел в кожній групі буде практично однаковою, тому можемо для кожної пари груп перебрати всі варіанти вибору двох чисел з них. Таким чином складність буде \(O(3^B * (T / 2^B)^2) = O(T^2 / (4/3)^B)\), тому виберемо досить велике \(B\), наприклад \(B = 16\).
Альтернативний розв’язок. Побудуємо префіксне дерево по двійкових представленнях всіх щасливих чисел. Тепер для кожного числа \(x\) будемо шукати всі числа \(y > x\) та \(y AND x = 0\). Для цього будемо робити пошук, починаючи з кореня префіксного дерева. Якщо зараз стоїмо у вершині \(v\), а черговий біт у числі \(х\) встановлений, то в \(y\) він має бути відсутній, тому маємо лише один перехід. Якщо ж цей біт у \(х\) відсутній, то спустимося до обох синів \(v\) (якщо такі існують), та шукатимемо \(y\) в них обох. З огляду на випадковість двійкового представлення щасливих чисел, такий розв’язок достатньо швидкий для заданих обмежень.
Спершу покажемо, що завжди існує дерево бамбук, яке схоже на будь-яке оригінальне дерево. Бамбук – дерево, в якому всі вершини розташовані в ряд та кожна вершина з’єднана ребром зі своїми сусідами.
Доведемо це методом математичної індукції. Розглянемо найбільше ребро, видалимо його, таким чином розділимо дерево на 2 частини. Зауважимо, що ми можемо отримати схоже дерево бамбук для обох частин, а потім з’єднати їх видаленим ребром.
Повернемось до оригінальної задачі. Будемо додавати вершини по одній та будувати дерево бамбук. Запитаємо максимальну вагу ребра на шляху від нової вершини до центральної в бамбуку. Якщо таке значення ваги вже було раніше, то ми знаємо, з якої сторони від центральної вершини, повинна знаходитись нова вершина. Припустимо такого значення не було. Нехай це значення \(w\). Знайдемо перше ребро справа від центральної вершини з вагою більшою за \(w\). Вставимо нову вершину в середину цього ребра. Якщо такого ребра не існує, то вставимо нову вершину в кінець масиву. Можна показати, що таке дерево буде схожим на оригінальне. Тобто при додаванні нової вершини ми можемо використати двійковий пошук, щоб знайти куди можливо її вставити.
Також існує рандомізований розв’язок. Візьмемо випадкову вершину, знайдемо ваги від неї до всіх інших вершин. Поділимо всі вершини на групи з однаковим значенням, розв’яжемо задачу для кожної групи окремо, після цього зробимо бамбук, в якому впорядкуємо групи за значенням.
Скажемо, що кожна намистинка вказує найближчу намистинку такого ж кольору. Якщо \(d_i > 0\), то намистинка на позиції \(i\) може вказувати або на намистинку \(i-d_i\) або на намистинку \(i+d_i\).
Для того, щоб потрібне намисто існувало необхідно і достатньо, щоб виконувались умови:
Жодна намистинка не може вказувати на намистинку з більшим значенням \(d\) чи значенням 0.
Якщо намистинка \(x\) вказує вправо на намистинку \(y\), то намистинка \(y\) може вказувати вліво лише у випадку, якщо \(d_x=d_y\), тобто намистинка \(y\) вказує на намистинку \(x\)(і навпаки).
Не може існувати двох намистинок, які вказується вправо на ту ж намистинку(і навпаки).
Розв’яжемо задачу алгоритмом 2-SAT. Для кожної намистинки зробимо змінну, яка рівна true, якщо намистинка вказує вправо та false, якщо вліво.
Перша умова вказує, що деякі змінні не можуть приймати значення true чи false. Щоб задовольнити другу умову потрібно додати \(O(n)\) обмежень задачі 2-SAT.
Для третьої умови, нехай намистинки \(x_1, x_2, \dots, x_k\) усі вказують вліво на намистинку \(y\). Тоді нам потрібно додати обмеження \(x_i | x_j\) для усіх \(i \ne j\), яких може бути \(O(n^2)\). Подивимось, які ребра ми додаємо в граф для розв’язку задачі: це будуть усі ребра \(!x_i \to x_j\) для \(i \ne j\). Тобто нам потрібно, щоб з кожного \(!x_i\) були досяжні усі інші \(x_j\) крім \(x_i\). Додамо додаткові вершини \(p_i\), з якої досяжні усі змінні на префіксі \(x_1, x_2, \dots, x_i\). Для цього додамо по 2 ребра \(p_i \to p_{i-1}\) та \(p_i \to x_i\). Аналогічно додамо додаткові вершини \(s_i\), які відповідають за суфікси. Після цього ми можемо додати 2 ребра \(!x_i \to p_{i-1}\) та \(!x_i \to s_{i+1}\). Таким чином ми отримали граф з такими ж властивостями, як в графа 2-SAT, але в ньому O(n) вершин та ребер.