Subtask 1

For every segment between ~i~ and ~i+1~, we can either direct it from ~i~ to ~i+1~ or we can direct it from ~i+1~ to ~i~. This means that every segment has two different states. So, we can try all ~2^{N-1}~ different configurations and find the minimal one. We can find the number of pairs for each configuration in ~\mathcal{O}(N)~ time.

Time complexity: ~\mathcal{O}(2^NN)~

Subtask 2

We can think about this problem as partitioning the segments into multiple contiguous parts where every segment in one part has the same orientation and different orientation from the adjacent contiguous parts. We will try to apply dynamic programming to this program. ~dp[n][k]~ will be a boolean. ~dp[n][k]~ is true when it is possible to get ~k~ pairs among the first ~n~ friends and false otherwise. To find whether ~dp[n][k]~ is true or not, we can try to consider every suffix ~[m, n]~ where ~1 \le m < n~ is a contiguous segment described above. So, we have

$$\displaystyle dp[n][k] = \begin{cases} true, & \text{if } dp[m][k - c_{m, n}] \text{ is true} \\ false, & \text{otherwise} \end{cases}$$

where ~c_{m, n}~ is the number of pairs of the same element in the subarray ~[m, n]~. We can quickly compute ~c_{m, n}~ by adding the number of other elements that are equal to ~a_m~ in ~[m+1, n]~ to ~c_{m, n}~. This can be done quickly by having a frequency array. Thus, it is possible to have ~\mathcal{O}(N^3)~ states and ~\mathcal{O}(N)~ transition.

Time Complexity: ~\mathcal{O}(N^4)~

Subtask 3

Note that for a fixed ~n~ and ~m~, then for all ~k~, if ~dp[m][k - c_{m, n}]~ is true, then ~dp[n][k]~ is true. Since ~c_{m, n}~ is constant, then we can simulate all ~k~ together with a bitset by getting the Bitwise Or of ~dp[m]~ shifted to the left by ~c_{m, n}~ with the current ~dp[n]~ for each ~m~.

Time Complexity: ~\mathcal{O}(\frac{N^4}{W})~ where ~W~ is the word size. In our case, ~W=64~.

Subtask 4

Note that we have ~\mathcal{O}(N^3)~ states, so we cannot compute all the states if we want to solve for ~N \le 1000~. We want to find some structure of ~dp[i][*]~ that allows us to compute less states. Define ~mn[i]~ to be minimal such that ~dp[i][mn[i]] = true~, define ~mx[i]~ to be the maximal such that ~dp[i][mx[i]]=true~, define ~b[i]~ to be the maximal such that ~\forall mn[i] \le j \le b[i]~, ~dp[i][j] = true~. We can calculate ~mn[i]~, ~mx[i]~, in ~\mathcal{O}(N^2)~ time. Define ~seg[i] \subseteq [mn[i],b[i]]~ recursively as ~seg[1] = [0,0]~ and ~seg[i] = \cup_{j=1}^{i-1} seg[j]+c_{j,i}~. We claim that ~\frac{|seg[i]|}{mx[i]-mn[i]+1}~ is large ~(>0.9)~ for large ~N~. Some intuition for this is: ~seg[i] \supseteq seg[i-1]+(c_{i-1,i} \in \{0,1\})~, ~seg[i]~ will be extended if there exists ~j~ such that ~mn[j]+c_{j,i} \le \max(seg[i])~ and ~\max(seg[j])+c_{j,i} > \max(seg[i])~. Since ~c_{j,i} - c_{j-1,i}~ is bounded by ~i~, and ~seg[j]~ is large for ~j<i~ by induction, such a segment must exist.

Once we have that ~seg[i]~ is large, for ~N \le 1000~, we can only compute states ~dp[n][k]~ where ~k > \max(seg[n])~, which turns out to be very few states for ~N \le 1000~, but this is not enough for full points.

Subtask 5

Note that since we are only considering states where ~k~ is very large, the number of ~j~ that we can transition to from ~i~ is very small. For each ~i~, we can precompute the order in which we can transition to ~j~ for all ~1 \le j < i~ in ~\mathcal{O}(N^2 \log N)~ time. Then, when solving for ~dp[i][k]~, we can binary search for the first ~j~ in the order that we can transition to, instead of looping over all possible transitions. With these observations, we compute far less states than in the Subtask 4 solution, and compute each state much faster, allowing us to solve for ~N \le 5000~.

If you have a proof or countercase for this solution, feel free to put it in the comments.