Subtask 1

The first subtask was to reward brute force solutions.

Time Complexity: ~\mathcal{O}(N \cdot 2^N)~ or similar.

Subtask 2

It can be proven that a rotational array ~a~ of length ~N~ has some subarray ~l~ that repeats over the entirety of ~a~. In addition, the length of this segment will be divisible by ~N~, or a factor of ~N~. Thus, ~length(a) \bmod length(l) = 0~. The proof for these is left as an exercise for the reader.

If we check for all ~1 \le N \le 10^5~, ~N~ has only so many factors. The maximum number of factors ~N~ has is ~128~ for ~N = 83160~. Thus, we can simply brute force, as ~128 \cdot N~ will pass!

We can loop from ~1~ to ~N-1~, and for all numbers ~k~ that are a factor of ~N~, assume that ~length(l) = k~. We then must make ~a_i = a_{k+i} = a_{2k+i} \ldots~ for all ~1 \le i < k~. Since ~a_i \in \{1, 2\}~ for this subtask, we can both: How many modifications are required to modify everything to ~1~? How many are required to modify everything to ~2~? Take the minimum of these.

Time Complexity: ~\mathcal{O}(N \cdot \sigma_0(N))~, where ~\sigma_0(N)~ is the number of factors of ~N~.

Subtask 3

Building onto subtask 2, we can see that the restriction on ~a_i~ has been removed. In addition going through all ~1 \le a_i \le 10^9~ is way too slow.

Let us remodel the problem of making ~a_i = a_{k+i} = a_{2k+i} \ldots~ for all ~1 \le i < k~. We can imagine placing points on a number line, where ~a_i~ is placed at the point ~a_i~. The problem now reduces to moving these points to a common integer location, where the distance they travel is their cost. It can shown that the lowest cost consists of moving all the points to the median of the set of points (see Geometric Median). This can be done in ~O \left(\frac{N \log N}{k} \right)~ time, multiplied by ~k~ for doing this for all ~1 \le i < k~ times.

Time Complexity: ~\mathcal{O}(N \log N \cdot \sigma_0(N))~, where ~\sigma_0(N)~ is the number of factors of ~N~.