A. Найбільша зростаюча підпослідовність
Завдання задачі — порахувати, скільки символів треба видалити в підрядку, аби він перетворився у паліндром.
Нехай dp[l][r] — відповідь на задачу для підвідрізка від l-го до r-го символа.
Початкові стани: для проміжка довжини 1 маємо dp[i][i]=0, а для проміжка довжини 2 dp[i][i+1] дорівнює 0 або 1.
Для підрядків з довжиною хоча б 3 можемо розглянути крайні елементи. Якщо вони рівні (sl=sr), тоді ми можемо визначити що dp[l][r]=dp[l+1][r−1]. У випадку коли символи різні (sl≠sr), то треба видалити один із цих символів тобто dp[l][r]=min(dp[l][r−1],dp[l+1][r])+1.
Перш за все нам потрібно перевірити першу умову, що числа зростають.
Якщо це не так, тоді ми знаємо що відповідь — No..
Розглянемо таку динаміку: dp[s]= true/false — чи можна отримати суму чисел s використовуючи лише розглянуті числа.
Коли ми розглядаємо нове число a тоді якщо dp[s]=true, тоді ми можемо сказати що тепер dp[s+a]= true і це треба зробити по усіх значеннях s.
Ми будемо розглядати числа в порядку зростання. Перед тим як розглянути чергове число ai, перевіримо чи ми з менших чисел могли утворити суму рівну поточному числу (перевірити значення dp[ai]). Якщо dp[ai]= true, то це означає що порушується умова на супер послідовність.
Для розв’язання цієї задачі можна переформулювати задачу так: для кожного j треба порахувати мінімальну незбалансованість для j пар. Тоді щоб отримати відповідь на початкову задачу нам треба знайти найбільше j, для якого незбалансованість не перевищує k.
Посортуємо масив за зростанням. Оптимально парувати тільки ті елементи, які є сусідніми в посортованому масиві.
Нехай dp[i][j] — мінімальна незбалансованість, якщо ми розглянули перші i чисел та утворили з них j пар.
Маємо два переходи.
Спаруємо сусідні (у посортованому масиві) елементи ai−1 та ai. Оновимо dp[i][j] значенням dp[i−2][j−1]+(ai−ai−1).
Не паруємо ai із жодним іншим елементом. У цьому разі оновимо dp[i][j] значенням dp[i−1][j].
Позначимо f(m) відповідь на задачу залежно від кількості студентів m. Ця функція є опуклою вгору, тобто виконується f(m+2)−f(m+1)≤f(m+1)−f(m). Нам потрібно знайти відповідь для k студентів f(k).
Розглянемо функцію g(m)=f(m)−λm для деякого параметра λ. Функція g(m) також є опуклою вгору, як сума опуклої вгору та лінійної.
Термінами нашої задачі можна сказати, що g(m) — це максимальне задоволення студентів, щоб роздати пробірки m студентам, причому ми «платимо» (віднімаємо від задоволення) λ одиниць за кожного студента.
Тепер розглянемо дещо іншу задачу, ніж початкова. Потрібно роздати пробірки студентам, щоб максимізувати сумарне задоволення, коли за кожного студента «платимо» λ одиниць, причому дозволено роздати пробірки скільком завгодно студентам.
Цю задачу можна розв’язати таким динамічним програмуванням. Будемо підтримувати два значення в динаміці: dp[i].first — власне відповідь на задачу, коли розглянули перших i пробірок, і dp[i].second — оптимальна кількість студентів, яким потрібно роздати ці пробірки. Перехід динаміки: dp[i].first=maxjdp[j].first+c[j+1][i]−λ, де c[j+1][i] — кількість різних речовин на проміжку [j+1,i]. У цій динаміці в першу чергу максимізовуємо значення first, а в другу чергу максимізовуємо second.
Тоді dp[n].first — відповідь, коли роздамо всі n пробірок. Тут не накладаються обмеження на кількість студентів, тому dp[n].first=maxmg(m) — максимальному значенню функції g для всіх можливих кількостей студентів.
Позначимо mопт оптимальну кількість студентів для деякого параметра λ. Тобто dp[n].first=maxmg(m)=g(mопт). Якщо mопт=k, тоді можна знайти значення f(k)=g(k)+λk — це й буде відповіддю на задачу.
Як підібрати таке λ, щоб для нього виконувалося mопт=k? Зауважимо, що при λ=0 (нічого не «платимо» за кількість студентів), оптимально роздати пробірки n студентам, тобто mопт=n для λ=0. А коли λ=n (дорого «платити» за студентів), то вигідно взяти лише одного студента, тобто mопт=1 для λ=n. Чим більше λ, тим дорожче «платити» за студентів, тим буде меншою оптимальна кількість студентів mопт.
Для знаходження параметра λ скористаємось двійковим пошуком. Потрібно знайти таке найбільше λ, що mопт≥k, тобто dp[n].second≥k.
Відповіддю на задачу буде f(k)=g(mопт)+λk=dp[n].first+λk.
Складність розв’язку: O(n2logn).
Нехай dp[i][0] — відповідь на задачу для перших i місяців, якщо Зеник після цих місяців перебуває на загальній системі, а dp[i][1] — якщо на спрощеній.
Переходи динаміки:
Зеник був на загальній, залишається на загальній: dp[i][0]→dp[i+1][0].
Зеник був на загальній, переходить на спрощену: dp[i][0]→dp[i+1][1].
Зеник був на спрощеній, залишається на спрощеній: dp[i][1]→dp[i+1][1].
Зеник був на спрощеній, переходить на загальну: dp[i][1]→dp[k][0], де k=min(i+m,n). Тут ми повинні забезпечити, що Зеник залишатиметься на загальній системі принаймні m місяців (або до кінця).
Щоб відновити відповідь, потрібно для кожного стану dp підтримувати, яким попереднім станом ми його оновили.
Складність розв’язку: O(n).
Це задача про рюкзак.
Нехай dp[i][j] — максимальний прибуток, який ми отримаємо, якщо ми розглянули i холодильників, та купили холодильників на суму j гривень.
Переходи динаміки:
Не купуємо i-ий холодильник: dp[i][j]→dp[i+1][j].
Купуємо i-ий холодильник за ai гривень: dp[i][j]→dp[i+1][j+ai].
Складність розв’язку: O(n⋅max\_sum)=O(n⋅n⋅max\_a)=O(n2⋅max\_a).
Потрібно відсортувати чемодани за об’ємом. Після цього зробимо динаміку схожу на найдовшу зростаючу підпослідовність.
Послідовність довжини n≥2, яка задовольняє вимоги, має вигляд xxxxxxx=47xxxxx (якщо починається цифрою 4) або xxxxxxx=7xxxxxx (якщо починається цифрою 7).
Кількість потрібних рядків рядків довжини n порахуємо динамікою dp[n]=dp[n−2]+dp[n−1]. Значення динаміки — це послідовність чисел Фібоначчі, яка починається зі значень dp[0]=1,dp[1]=2.
Якщо k>dp[n], то відповіді не існує.
Щоб знайти k-у послідовність, ставимо цифри по черзі зліва направо.
Нехай n≥2. Тоді виконуємо такий процес.
Якщо k≤dp[n−2], то послідовність xxxxxxx має вигляд 47xxxxx. Ставимо цифри 47 і зменшуємо n на 2.
Якщо k>dp[n−2], то послідовність xxxxxxx має вигляд 7xxxxxx. Зменшуємо k на dp[n−2], ставимо цифру 7 і зменшуємо n на 1.
Порахуємо розмір кожної з компонент зв’язності. Тепер для кожної кількості балів від 0 до n порахуємо чи можемо ми її набрати. Це можна зробити за допомогою динаміки про рюкзак. Для оптимізації використаємо бітсети.
Нехай dp[i][j][0/1] — кількість щаслиих чисел довжини i, цифри змінюються j разів і визначена перша цифра (0 відповідає за 4, 1 відповідає за 7). Ми можемо легко перерахувати таку динаміку так:
dp[i+1][j][0] += dp[i][j][0]
dp[i+1][j+1][0] += dp[i][j][1]
dp[i+1][j+1][1] += dp[i][j][0]
dp[i+1][j][1] += dp[i][j][1]
Тепер переберемо довжину відповіді — len. Якщо ∑j∈luckydp[len][j][0]+dp[len][j][1] < n, то ця довжина є замалою. Коли ми переходимо до len+1, потрібно від n відняти кількість депутатських щасливих чисел довжини len. Тепер коли в нас є фіксована довжина, потрібно знайти n-е депутатське щасливе число число довжини len. Для цього будемо йти від старших цифр до молодших і пробувати жадібно ставити 4 або 7. Перевіряти чи можемо поставити ми будемо за допомогою порахованої перед тим динаміки.
Впорядкуємо відрізки за правим кінцем в порядку зростання. Якщо праві кінці збігаються, то за лівим у порядку спадання. Стиснемо координати і будемо розглядати тільки цікаві (ті які є кінцем хоча б одного відрізка).
Порахуємо динаміку dp[x] — відповідь на задачу, якщо останній відрізок, який ми взяли має лівий кінець в координаті x. Коли ми розглядаємо i-тий відрізок, то ми вже розглянути всі, які закінчуються раніше. Нам підходять всі відрізки, у яких лівий кінець є лівіше ніж лівий кінець i-того відрізка. Оновимо dp[l[i]]=maxx<l[i]dp[x]+1. Щоб шукати максимум використаємо дерево Фенвіка або дерево відрізків.
Розбір задачі доступний на сайті - Обласна iнтернет олiмпiада 2023 - Тур 2 (розбір).