A. Найбільша зростаюча підпослідовність
Завдання задачі — порахувати, скільки символів треба видалити в підрядку, аби він перетворився у паліндром.
Нехай \(\text{dp}[l][r]\) — відповідь на задачу для підвідрізка від \(l\)-го до \(r\)-го символа.
Початкові стани: для проміжка довжини \(1\) маємо \(\text{dp}[i][i] = 0\), а для проміжка довжини \(2\) \(\text{dp}[i][i + 1]\) дорівнює \(0\) або \(1\).
Для підрядків з довжиною хоча б \(3\) можемо розглянути крайні елементи. Якщо вони рівні (\(s_l = s_r\)), тоді ми можемо визначити що \(\text{dp}[l][r] = \text{dp}[l + 1][r - 1]\). У випадку коли символи різні (\(s_l \ne s_r\)), то треба видалити один із цих символів тобто \(\text{dp}[l][r] = \min (\text{dp}[l][r - 1], \text{dp}[l + 1][r]) + 1\).
Перш за все нам потрібно перевірити першу умову, що числа зростають.
Якщо це не так, тоді ми знаємо що відповідь — No..
Розглянемо таку динаміку: \(\text{dp}[s] =\) true/false — чи можна отримати суму чисел \(s\) використовуючи лише розглянуті числа.
Коли ми розглядаємо нове число \(a\) тоді якщо \(dp[s] =\)true, тоді ми можемо сказати що тепер \(\text{dp}[s + a] =\) true і це треба зробити по усіх значеннях \(s\).
Ми будемо розглядати числа в порядку зростання. Перед тим як розглянути чергове число \(a_i\), перевіримо чи ми з менших чисел могли утворити суму рівну поточному числу (перевірити значення \(\text{dp}[a_i]\)). Якщо \(\text{dp}[a_i] =\) true, то це означає що порушується умова на супер послідовність.
Для розв’язання цієї задачі можна переформулювати задачу так: для кожного \(j\) треба порахувати мінімальну незбалансованість для \(j\) пар. Тоді щоб отримати відповідь на початкову задачу нам треба знайти найбільше \(j\), для якого незбалансованість не перевищує \(k\).
Посортуємо масив за зростанням. Оптимально парувати тільки ті елементи, які є сусідніми в посортованому масиві.
Нехай \(\text{dp}[i][j]\) — мінімальна незбалансованість, якщо ми розглянули перші \(i\) чисел та утворили з них \(j\) пар.
Маємо два переходи.
Спаруємо сусідні (у посортованому масиві) елементи \(a_{i-1}\) та \(a_i\). Оновимо \(\text{dp}[i][j]\) значенням \(\text{dp}[i - 2][j - 1] + (a_i - a_{i - 1})\).
Не паруємо \(a_i\) із жодним іншим елементом. У цьому разі оновимо \(\text{dp}[i][j]\) значенням \(\text{dp}[i - 1][j]\).
Позначимо \(f(m)\) відповідь на задачу залежно від кількості студентів \(m\). Ця функція є опуклою вгору, тобто виконується \(f(m + 2) - f(m + 1) \le f(m + 1) - f(m)\). Нам потрібно знайти відповідь для \(k\) студентів \(f(k)\).
Розглянемо функцію \(g(m) = f(m) - \lambda m\) для деякого параметра \(\lambda\). Функція \(g(m)\) також є опуклою вгору, як сума опуклої вгору та лінійної.
Термінами нашої задачі можна сказати, що \(g(m)\) — це максимальне задоволення студентів, щоб роздати пробірки \(m\) студентам, причому ми «платимо» (віднімаємо від задоволення) \(\lambda\) одиниць за кожного студента.
Тепер розглянемо дещо іншу задачу, ніж початкова. Потрібно роздати пробірки студентам, щоб максимізувати сумарне задоволення, коли за кожного студента «платимо» \(\lambda\) одиниць, причому дозволено роздати пробірки скільком завгодно студентам.
Цю задачу можна розв’язати таким динамічним програмуванням. Будемо підтримувати два значення в динаміці: \(\text{dp}[i].\text{first}\) — власне відповідь на задачу, коли розглянули перших \(i\) пробірок, і \(\text{dp}[i].\text{second}\) — оптимальна кількість студентів, яким потрібно роздати ці пробірки. Перехід динаміки: \(\text{dp}[i].\text{first} = \max_j \text{dp}[j].\text{first} + c[j + 1][i] - \lambda\), де \(c[j + 1][i]\) — кількість різних речовин на проміжку \([j + 1, i]\). У цій динаміці в першу чергу максимізовуємо значення \(\text{first}\), а в другу чергу максимізовуємо \(\text{second}\).
Тоді \(\text{dp}[n].\text{first}\) — відповідь, коли роздамо всі \(n\) пробірок. Тут не накладаються обмеження на кількість студентів, тому \(\text{dp}[n].\text{first} = \max_m g(m)\) — максимальному значенню функції \(g\) для всіх можливих кількостей студентів.
Позначимо \(m_\text{опт}\) оптимальну кількість студентів для деякого параметра \(\lambda\). Тобто \(\text{dp}[n].\text{first} = \max_m g(m) = g(m_\text{опт})\). Якщо \(m_\text{опт} = k\), тоді можна знайти значення \(f(k) = g(k) + \lambda k\) — це й буде відповіддю на задачу.
Як підібрати таке \(\lambda\), щоб для нього виконувалося \(m_\text{опт} = k\)? Зауважимо, що при \(\lambda = 0\) (нічого не «платимо» за кількість студентів), оптимально роздати пробірки \(n\) студентам, тобто \(m_\text{опт} = n\) для \(\lambda = 0\). А коли \(\lambda = n\) (дорого «платити» за студентів), то вигідно взяти лише одного студента, тобто \(m_\text{опт} = 1\) для \(\lambda = n\). Чим більше \(\lambda\), тим дорожче «платити» за студентів, тим буде меншою оптимальна кількість студентів \(m_\text{опт}\).
Для знаходження параметра \(\lambda\) скористаємось двійковим пошуком. Потрібно знайти таке найбільше \(\lambda\), що \(m_\text{опт} \ge k\), тобто \(\text{dp}[n].\text{second} \ge k\).
Відповіддю на задачу буде \(f(k) = g(m_\text{опт}) + \lambda k = \text{dp}[n].\text{first} + \lambda k\).
Складність розв’язку: \(O(n^2 \log n)\).
Нехай \(\text{dp}[i][0]\) — відповідь на задачу для перших \(i\) місяців, якщо Зеник після цих місяців перебуває на загальній системі, а \(\text{dp}[i][1]\) — якщо на спрощеній.
Переходи динаміки:
Зеник був на загальній, залишається на загальній: \(\text{dp}[i][0] \to \text{dp}[i + 1][0]\).
Зеник був на загальній, переходить на спрощену: \(\text{dp}[i][0] \to \text{dp}[i + 1][1]\).
Зеник був на спрощеній, залишається на спрощеній: \(\text{dp}[i][1] \to \text{dp}[i + 1][1]\).
Зеник був на спрощеній, переходить на загальну: \(\text{dp}[i][1] \to \text{dp}[k][0]\), де \(k = \min (i + m, n)\). Тут ми повинні забезпечити, що Зеник залишатиметься на загальній системі принаймні \(m\) місяців (або до кінця).
Щоб відновити відповідь, потрібно для кожного стану \(\text{dp}\) підтримувати, яким попереднім станом ми його оновили.
Складність розв’язку: \(O(n)\).
Це задача про рюкзак.
Нехай \(\text{dp}[i][j]\) — максимальний прибуток, який ми отримаємо, якщо ми розглянули \(i\) холодильників, та купили холодильників на суму \(j\) гривень.
Переходи динаміки:
Не купуємо \(i\)-ий холодильник: \(\text{dp}[i][j] \to \text{dp}[i + 1][j]\).
Купуємо \(i\)-ий холодильник за \(a_i\) гривень: \(\text{dp}[i][j] \to \text{dp}[i + 1][j + a_i]\).
Складність розв’язку: \(O(n \cdot \text{max\_sum}) = O(n \cdot n \cdot \text{max\_a}) = O(n^2 \cdot \text{max\_a})\).
Потрібно відсортувати чемодани за об’ємом. Після цього зробимо динаміку схожу на найдовшу зростаючу підпослідовність.
Послідовність довжини \(n \ge 2\), яка задовольняє вимоги, має вигляд \(xxxxxxx = 47xxxxx\) (якщо починається цифрою \(4\)) або \(xxxxxxx = 7xxxxxx\) (якщо починається цифрою \(7\)).
Кількість потрібних рядків рядків довжини \(n\) порахуємо динамікою \(\text{dp}[n] = \text{dp}[n - 2] + \text{dp}[n - 1]\). Значення динаміки — це послідовність чисел Фібоначчі, яка починається зі значень \(\text{dp}[0] = 1, \text{dp}[1] = 2\).
Якщо \(k > \text{dp}[n]\), то відповіді не існує.
Щоб знайти \(k\)-у послідовність, ставимо цифри по черзі зліва направо.
Нехай \(n \ge 2\). Тоді виконуємо такий процес.
Якщо \(k \le \text{dp}[n - 2]\), то послідовність \(xxxxxxx\) має вигляд \(47xxxxx\). Ставимо цифри \(47\) і зменшуємо \(n\) на \(2\).
Якщо \(k > \text{dp}[n - 2]\), то послідовність \(xxxxxxx\) має вигляд \(7xxxxxx\). Зменшуємо \(k\) на \(\text{dp}[n - 2]\), ставимо цифру \(7\) і зменшуємо \(n\) на \(1\).
Порахуємо розмір кожної з компонент зв’язності. Тепер для кожної кількості балів від 0 до \(n\) порахуємо чи можемо ми її набрати. Це можна зробити за допомогою динаміки про рюкзак. Для оптимізації використаємо бітсети.
Нехай \(\text{dp}[i][j][0/1]\) — кількість щаслиих чисел довжини \(i\), цифри змінюються \(j\) разів і визначена перша цифра (0 відповідає за 4, 1 відповідає за 7). Ми можемо легко перерахувати таку динаміку так:
\(\text{dp}[i + 1][j][0]\) += \(\text{dp}[i][j][0]\)
\(\text{dp}[i + 1][j + 1][0]\) += \(\text{dp}[i][j][1]\)
\(\text{dp}[i + 1][j + 1][1]\) += \(\text{dp}[i][j][0]\)
\(\text{dp}[i + 1][j][1]\) += \(\text{dp}[i][j][1]\)
Тепер переберемо довжину відповіді — \(len\). Якщо \(\sum_{j \in lucky} dp[len][j][0] + dp[len][j][1]\) < \(n\), то ця довжина є замалою. Коли ми переходимо до \(len + 1\), потрібно від \(n\) відняти кількість депутатських щасливих чисел довжини \(len\). Тепер коли в нас є фіксована довжина, потрібно знайти \(n\)-е депутатське щасливе число число довжини \(len\). Для цього будемо йти від старших цифр до молодших і пробувати жадібно ставити 4 або 7. Перевіряти чи можемо поставити ми будемо за допомогою порахованої перед тим динаміки.
Впорядкуємо відрізки за правим кінцем в порядку зростання. Якщо праві кінці збігаються, то за лівим у порядку спадання. Стиснемо координати і будемо розглядати тільки цікаві (ті які є кінцем хоча б одного відрізка).
Порахуємо динаміку \(\text{dp}[x]\) — відповідь на задачу, якщо останній відрізок, який ми взяли має лівий кінець в координаті \(x\). Коли ми розглядаємо \(i\)-тий відрізок, то ми вже розглянути всі, які закінчуються раніше. Нам підходять всі відрізки, у яких лівий кінець є лівіше ніж лівий кінець \(i\)-того відрізка. Оновимо \(\text{dp}[l[i]] = \max_{x < l[i]}{\text{dp}[x] + 1}\). Щоб шукати максимум використаємо дерево Фенвіка або дерево відрізків.
Розбір задачі доступний на сайті - Обласна iнтернет олiмпiада 2023 - Тур 2 (розбір).