Кожному коню необхідно 4 підкови, отже сумарно нам необхідно \(4 \cdot n\) підков.
Обмеження задачі дозволють перебрати кількість ящиків від 1 до \(4 \cdot n\) та перевірити, чи цієї кількості достатньо щоб підкувати всіх коней.
Також найменшу кількість ящиків можна було знайти формулою \(m = \lceil \frac{4 \cdot n}{k} \rceil\) — ділення \(4 \cdot n\) на \(k\) із заокругленням догори.
Знайшовши \(m\) можна порахувати відповідь за формулою \(m \cdot c\).
Код розв’язку мовою C++ з перебором \(m\)
Нехай \(s\) — сума поживностей трави на всьому пасовищі.
Зафіксуємо межу поділу пасовища. Нехай сума в лівій частині дорівнює \(p\). Тоді сума в правій частині буде \(s - p\). Відповідь для такого поділу буде \(p - (s - p) = 2 \cdot p - s\).
Отже, можна перебрати межу зліва направа, підтримуючи змінну \(p\). Коли пересуваємо паркан на одну ділянку праворуч, то до лівої частини долучається нова ділянка і до \(p\) додається значення поживності трави на цій ділянці.
Задача полягає в тому, щоб знайти, на яку найменшу кількість груп треба поділити коней, так аби можна було їх впорядкувати. Позначимо цю кількість \(m\). Якщо \(m \le k\), відповідь — так, інакше — ні.
Розглянемо двох коней \(p_i\) та \(p_{i+1}\), що стоять поруч.
Якщо \(p_{i+1} = p_i + 1\), то ці коні після впорядкування також стоятимуть поруч, тому нема сенсу їх розділяти на різні групи.
Якщо ж \(p_{i+1} \ne p_i + 1\), коні вже не стоятимуть поруч, тому їх обов’язково треба розділити на різні групи.
Отже, щоб знайти \(m\), треба порахувати кількість таких позицій \(i\), що \(p_{i+1} \ne p_i + 1\), та додати до цієї кількості одиницю (якщо коні вже стоять у правильному порядку, то \(m=1\)).
Переформулюємо задачу. Задано рядок \(s\) з 0 і 1.
Запит першого типу присвоює першим \(i\) символам задане значення, а запит
другого типу — знайти символ в \(i\)-й
позиції.
У цій задачі будемо підтримувати проміжки однакових значень у рядку \(s\).
Наприклад, \(s =
\,\)000011100111100000. Перший проміжок закінчується
в позиції \(4\) та складається із
символів 0. Позначимо цей проміжок (\(4\), 0). Другий проміжок
закінчується в позиції \(7\) та
складається із символів 1. Позначимо його (\(7\), 1). Усі проміжки для
рядка \(s\): (\(4\), 0), (\(7\), 1), (\(9\), 0), (\(13\), 1), (\(18\), 0).
Якщо надійде запит присвоїти першим \(8\) символам рядка значення 1,
рядок перетвориться на 111111110111100000. Проміжки для
нового рядка: (\(8\), 1),
(\(9\), 0), (\(13\), 1), (\(18\), 0).
Як видно з прикладу, запит першого типу видалить деякі проміжки з початку, та вставить один проміжок замість них.
Розгляньмо запит другого типу. Нехай потрібно знайти символ на \(i\)-ій позиції. Для цього треба знайти
проміжок, який містить цю позицію. Це проміжок, що закінчується в
позиції \(\ge i\), у якого позиція
закінчення найменша. У нашому прикладі для \(i
= 11\) це проміжок (\(13\),
1).
Щоб розв’язати задачу, будемо підтримувати згадані проміжки в порядку
справа наліво (у спадному порядку позицій закінчення проміжків). У
C++ можна використати
vector<pair<int, char>>.
Для запиту першого типу треба видалити деякі проміжки з кінця
(pop_back) та вставити в кінець
(push_back).
Щоб відповісти на запит другого типу, знайдемо потрібний проміжок двійковим пошуком. Якщо ви не знайомі із цим алгоритмом, наполегливо рекомендуємо прослухати відеолекцію на YouTube каналі Алготестера.
Тепер оцінимо складність розв’язку.
Перед усіма запитами є \(O(n)\)
проміжків. Для кожного запиту першого типу додасться один новий
проміжок. Тому загальна кількість усіх доданих проміжків упродовж роботи
алгоритму — \(O(n + q)\). А скільки
може бути видалень проміжків (pop_back)? Спершу може
здатися, що оскільки всього є \(O(n +
q)\) проміжків, то для кожного запиту першого типу буде \(O(n + q)\). Однак кожен проміжок буде
видалено не більше ніж один раз. Тому загальна кількість видалень також
\(O(n + q)\).
Для кожного запиту другого типу ми виконуємо двійковий пошук за \(O(\log (n + q))\).
Загальна складність: \(O(n + q + q \log (n + q)) = O(n + q \log (n + q))\).
Розв’яжемо задачу для \(n = 1\). Порахуємо для кожної ділянки, який у ній утворюється рівень шуму.
Коня з ділянки \(j\) чутно на ділянці \(y\) (\(j \le y\)) з гучністю \(\max(0, a_{1, j} - (y - j))\). Вираз \(a_{1, j} - (y - j) = (a_{1, j} + j) - y\) містить доданок \(y\), який не залежить від того якого коня вибрали, та доданок \(a_{0, j} + j\), що залежить лише від коня.
Будемо ітеруватись зліва направо по клітинках і пам’ятати максимальне значення \(a_{1, j} + j\) по усіх конях зліва. Віднявши від цього максимального значення \(y\), отримаємо рівень шуму який утворюють коні зліва. Аналогічно для кожної клітинки порахуємо який шум утворюється справа. Отже, шум який утворюють коні в цій клітинці рівний більшому зі значень шумів зліва та справа. Відповідно маючи рівень шуму в усіх клітинках, ми можемо знайти мінімальне значення шуму.
Якщо ж \(n \ne 1\) тоді ми поле можемо розділити на 4 чверті відносно ділянки \((x, y)\): ліву нижню, ліву верхню, праву нижню та праву верхню. Розглянемо лише одну чверть, де коні стоять у таких клітинках \((i, j)\) що \(i \le x\) та \(j \le y\).
Серед коней що мають \(i \le x\) та \(j \le y\) потрібно знайти найбільше значення \(a_{i, j} - (x - i) - (y - j) = (a_{i, j} + i + j) - (x + y)\). Тут аналогічно є доданок, що залежить лише від ділянки і доданок, що залежить лише від коня. Враховуючи це, можемо зробити аналогічно до \(n = 1\), тобто порахувати максимальне значення \(a_{i, j} + i + j\) по всіх конях що \(i \le x\) та \(j \le y\) — назвемо це значення \(mx(x, y)\). Значення \(mx(x, y)\) рівне \(\max(mx(x - 1, y), mx(x, y - 1), a_{x, y} + x + y)\).
Так ми врахували коней, що пасуться лише в одній чверті відносно ділянки \((x, y)\). Щоб урахувати всі 4 чверті, 4 рази повернемо матрицю на 90 градусів.
Розв’яжемо задачу окремо для паліндромів парної та непарної довжин.
Якщо в нас є паліндром \(p\) довжини
\(x > 1\), тоді якщо відкинути
перший і останній символ такого паліндрому, то отримаємо паліндром
довжини \(x - 2\). Напркилад, якщо
\(p\) = abbcbba, то
відкинувши перший і останній символи отримаємо bbcbb, що
теж є паліндромом. Ми так можемо відкидати символи, поки їх хоча б 3. Те
що залишилося після такого процесу, назвемо центром паліндрома. Для
непархних паліндромів, центр це один символ, для парних — нуль.
Розв’яжемо задачу для непарних паліндромів. Будемо перебирати символи зліва направо і пробувати покращити ними відповідь. Початково відповідь для першого символу 1. Нехай ми розглянули перші \(i - 1\) символи, як центри і найкраща відповідь це \(len\). Тоді для центру \(i\) нам цікаво чи можемо ми покращити відповідь. Зробимо запит непарного паліндрому з центром в \(i\)-тому символі і довжиною \(len + 2\). Якщо ми отримуємо відповідь, що такий підрядок є паліндромом, то оновимо відповідь і запитаємо чи є паліндромом рядок з центром в символі \(i\) і довжиною \(len + 4\). Будемо пробувати збільшувати довжину, поки наш запит не вилазить за межі рядка і ми отримали ствердну відповідь на попереднє запитання.
Порахуємо кількість запитів, яку ми використали. Кожен раз коли ми отримали ствердну відповідь, то розмір найбільшого паліндрому збільшується на 2, тобто це буде зроблено не більше ніж \(\frac{n}{2}\) разів. Для кожного центру, коли ми отримуємо відповідь 0, то перестаємо робити запити з цим центром, відповідно таких запитів буде не більше ніж \(n\).
Для парних паліндромів розв’яжемо аналогічно, тому загальна кількість запитів буде не більшою ніж \(3 \cdot n\).
Переформулюємо задачу наступним чином: Для всіх перестановок порахуємо кількість разів, коли елемент є максимумом на своєму префіксі.
Змінимо порядок сумування, тепер нам потрібно для кожної позициї порахувати у скількох перестановках елемент на цій позиції є максимумом на префіксі.
Розглянемо позицію \(i\). Назвемо перестановку хорошою, якщо елемент позиції \(i\) є максимумом на префіксі. Спочатку погрупуємо перестановки по тому, які елементи знаходяться на префіксі довжини \(i\). Таких груп буде \(C_n^i\). Для кожної групи порахуємо скільки є хороших перестановок.
Для групи, ми знаємо які елементи є на префіксі на префіксі довжини \(i\). Для хороших перестановок максимум з них буде на позиції \(i\). Всі інші елементи можна поставити в довільному порядку. Кількість способів розмістити елементи на префіксі є \((i - 1)!\) способів, а на суфіксі — \((n - i)!\). Відповідно в групі буде \((i - 1)! \cdot (n - i)!\) хороших перестановок.
Загальна формула виглядатиме так: \(\sum_{i = 1}^{n} C_n^i \cdot (i - 1)! \cdot (n - i)!\).