Author: | Oleksandr Tymkovych |
Task preparation: | Oleksandr Tymkovych, Pavlo Tsitsei |
Editorial: | Oleksandr Tymkovych |
Block : a_i \geq 1: The main observation is that the array has no segment of length \ell\in \{2, 3, \dots, n\} with a major element if and only if the array has no segment of length \ell \in \{2, 3\} with a major element.
Block : a_i = 0: For k\geq 3 one of the possible answers is a=[1,2,3,1,2,3,1,2,3,\dots]. For k < 3 the answer is almost always , except for sufficiently small where the previous construction works as well.
Block : there is no i>1 such that a_i = a_{i-1} = 0: For each unknown element, we know it's both neighbors (if they exist). The solution is similar to k>5 with some corner cases.
Block : k > 5: For k>5 we can do greedy replacing each unknown element with \texttt{mex}\{a_{i-2}, a_{i-1}, a_{i}, a_{i+1}, a_{i+2}\}.
Block : k \le 5: For k\le 5 the author's approach included dynamic programming with some of the states meaning the last three values solving the sub-problem on the array [a_1,\dots, a_i].
Block : without additional constraints: Combine the solutions of blocks and .