Сирна пастка#12998

Сирна пастка (Розбір)

Джеррі зупиняється, коли їсти далі невигідно, тож для довільного масиву виконано

c_i = \max(0,\ a_i + c_{i+1})

— за умови, що сума всього кола не додатна, інакше найкращим префіксом може виявитися все коло.

Спробуємо взяти a_i = c_i - c_{i+1} (індекси циклічні). Ці різниці задовольняють рівняння одразу для всіх , але їхня сума дорівнює нулю, а при нульовій сумі рівняння мають цілу сім'ю розв'язків: разом із їм задовольняє і , зменшене на будь-яку сталу до появи нуля. Реальний масив префіксних максимумів — найменший з них, тобто , зменшене на . Тому при \min c = 0 такий масив уже підходить, а при \min c = \mu > 0 відповідь буде зсунута вниз на .

Виправляє це одне число. Нехай — позиція мінімуму . Додамо до елемента a_{m-1} (циклічно). Тепер сума кола дорівнює рівно , отже кожен старт може з'їсти все коло і отримати щонайменше ; для стартів, у яких c_i > \mu, максимум і далі досягається на короткому префіксі й не змінюється, а старт отримує рівно . Саме тому доданок ставиться безпосередньо перед мінімальним стартом: тоді для нього повне коло — єдиний спосіб набрати .

Для прикладу c = [5, 2, 1] маємо \mu = 1 у позиції , різниці дають [3, 1, -4], а після додавання до a_2 — [3, 2, -4].

Складність: .

Для цього етапу офіційного розбору опубліковано не було; цей текст написано для архіву за розв'язком, який перевірено на задачі.