Автор: | Олександр Тимкович |
Підготовка задачі: | Олександр Тимкович, Павло Ціцей |
Розбір: | Олександр Тимкович |
Блок : a_i \geq 1: Основне спостереження полягає в тому, що масив не має відрізка довжини \ell\in \{2, 3, \dots, n\} з мажоруючим елементом тоді і тільки тоді, коли масив не має відрізка довжини \ell \in \{2, 3\} з мажоруючим елементом.
Блок : a_i = 0: Для k\geq 3 одна з можливих відповідей - a=[1,2,3,1,2,3,1,2,3,\dots]. Для k < 3 відповідь майже завжди , за винятком достатньо малих , де попередня конструкція також працює.
Блок : немає i>1, так що a_i = a_{i-1} = 0: Для кожного невідомого елемента ми знаємо обох сусідів (якщо вони існують). Рішення подібне до k>5 з деякими крайніми випадками.
Блок : k > 5: Для k>5 ми можемо використовувати жадібний підхід, замінюючи кожен невідомий елемент на \texttt{mex}\{a_{i-2}, a_{i-1}, a_{i}, a_{i+1}, a_{i+2}\}.
Блок : k \le 5: Для k\le 5 підхід автора включав динамічне програмування, де деякі стани означали останні три значення, що вирішують підзадачу на масиві [a_1,\dots, a_i].
Блок : без додаткових обмежень: Поєднайте рішення блоків і .