Subtask 1

Under the constraints of Subtask 1, we can try all ~N!~ possibilities ways to draw line segments. Since we can calculate the intersection number in ~\mathcal{O}(N^2)~ time, this subtask can be solved in ~\mathcal{O}(N^2 N!)~ time.

Subtasks 2, 3

Let ~w_1, w_2, \dots, w_N~ be the positions of the white points in ascending order. Similarly, let ~b_1, b_2, \dots, b_N~ be the positions of the black points in ascending order. Then, we shall prove that the best way to draw line segments is to connect ~w_i~ with ~b_{i+k}~ for every ~i~ for some integer ~k~. Here ~i~ is an integer from ~1~ to ~N~, and all indices are considered mod ~N~.

Consider the best way to draw line segments, and assume that ~w_i~ is connected with ~b_{p_i}~ by a line segment. First, we shall prove that, for different ~i~ and ~j~, the four points ~w_i, w_j, b_{p_j}, b_{p_i}~ are not located on the circle in this order (in the clockwise order). In fact, if ~w_i, w_j, b_{p_j}, b_{p_i}~ are located on the circle in this order, the intersection number will increase if we connect ~w_i~ with ~b_{p_j}~, and ~w_j~ with ~b_{p_i}~. It contradicts the assumption that we are considering the best way to draw line segments. Next, we shall show ~p_i-i \equiv p_{i+1}-(i+1)~ for every ~i~. If it is not satisfied for some ~i~, then there exists another black point ~b_{p_j}~ between ~b_{p_i}~ and ~b_{p_{i+1}}~. Now we consider the positions of the four points ~w_i, w_{i+1}, b_{p_i}, b_{p_{i+1}}~. By the above fact, ~w_i, w_{i+1}, b_{p_{i+1}}, b_{p_i}~ are not located in this order. Similarly, ~w_i, b_{p_i}, b_{p_{i+1}}, w_{i+1}~ are not located in this order. Assume that ~w_i, w_{i+1}, b_{p_i}, b_{p_{i+1}}~ are located in this order. Since there does not exist any white point between ~w_i~ and ~w_{i+1}~, the point ~w_j~ must lie between ~w_{i+1}~ and ~b_{p_j}~, or between ~b_{p_j}~ and ~w_i~. It contradicts the above fact. There are three remaining cases to consider, i.e., the case where ~w_i, b_{p_{i+1}}, b_{p_i}, w_{i+1}~ are located in this order, the case where ~w_i, b_{p_i}, w_{i+1}, b_{p_{i+1}}~ are located in this order, and the case where ~w_i, b_{p_{i+1}}, w_{i+1}, b_{p_i}~ are located in this order. Similarly, we can derive a contradiction in every case.

Therefore, the best way to draw line segments is to connect ~w_i~ with ~b_{i+k}~, for some integer ~k~. There are ~N~ candidates of the value of ~k~. For each ~k~, if we calculate the intersection number in ~\mathcal{O}(N^2)~ time, we can solve the task in ~\mathcal{O}(N^3)~ time in total. If we use data structure such as the Binary Indexed Tree or the Segment Tree, we can calculate the intersection number in ~\mathcal{O}(N \log N)~ time in the same way as calculating the number of transpositions of a permutation. The total time complexity is ~\mathcal{O}(N^2 \log N)~, and we can solve Subtask 3.

Subtask 4 (Full score solution)

Similarly as in Subtasks 2, 3, we fix an integer ~k~ and connect ~w_i~ with ~b_{i+k}~. We shall calculate the intersection number. For an index ~i~, we consider the number of line segments which intersect with the line segment connecting ~w_i~ with ~b_{i+k}~. We consider the two arcs whose endpoints are ~w_i, b_{i+k}~. Let ~L, R~ (~L \le R~) be the number of points on the arcs except for the endpoints. The number of line segments that intersect with the line segment connecting ~w_i~ with ~b_{i+k}~ is less than or equal to ~L~. We shall prove that the equality actually holds, i.e. ~L~ line segments intersect with the line segment connecting ~w_i~ with ~b_{i+k}~.

Take one of the two arcs such that the number of points in the fixed arc is smaller than or equal to the number of points in the other arc. We also take a point in the fixed arc. We may assume without loss of generality that we take a white point. We denote it by ~w_j~. Then, it is enough to prove that the four points ~w_i, w_j, b_{j+k}, b_{i+k}~ are not located in this order, in the clockwise order and in the counterclockwise order. We assume that these four points are located in this order in the clockwise order, and we shall derive a contradiction. We can treat the case of the counterclockwise order similarly.

By assumption, there are ~L~ points on the arc from ~w_i~ to ~b_{i+k}~. Since ~L+R = 2N-2~ and ~L \le R~, we have ~L \le N-1~, i.e., the number of points on the arc is less than or equal to ~N-1~. Changing the labels of the white points if necessary, we may assume that ~i < j~ holds. Then, the number of white points on the arc from ~w_i~ to ~w_j~ is ~j-i-1~, and the number of black points on the arc from ~b_{j+k}~ to ~b_{i+k}~ is ~N-(j-i+1)~. From this, we see that there are at least ~(j-i-1)+(N-(j-i+1))+2 = N~ points on the arc from ~w_i~ to ~b_{i+k}~, which is absurd.

Therefore, the number of line segments which intersect with the line segment connecting ~w_i~ with ~b_{i+k}~ is equal to the smaller number of points on the arcs between ~w_i~ and ~b_{i+k}~ except for the endpoints. (If the two arcs have the same number of points, we take any one of the two arcs.) By an appropriate case-by-case analysis, we can calculate this number by a linear function in terms of ~w_i~ and ~b_{i+k}~. Thus we can solve this task if we can add a linear function on an interval of ~k~ for each ~i~. This operation can be done in linear time by a cumulative sum technique. We need to find the interval where we will add a linear function. We can calculate it in linear time if we consider ~i~ in ascending order. In total, we can solve this task in ~\mathcal{O}(N)~ time.

Digression

Let ~f(k)~ be the intersection number for each ~k~. The function ~f(k)~ satisfies certain monotonicity condition. Precisely, if we consider the function ~f~ is defined on the integers mod ~N~, the following condition is satisfied.

Let ~a~ be the point where ~f~ takes the minimum, and ~b~ the point where ~f~ takes the maximum. Then, ~f~ is a monotone non-decreasing function in the interval ~a, a+1, \dots, b~, and it is a monotone non-increasing function in the interval ~b, b+1, \dots, a~.

To simplify the proof, we assume that the ~2N~ points divide the circle equally and the length of the circumference is ~2N~. For any two points ~p, q~ on the circle, let ~d(p, q)~ be the length of the shorter arc whose endpoints are ~p, q~. Let ~d'(p, q)~ be the distance from ~p~ to ~q~ in the clockwise direction. Let ~[p, q)~ be the arc from ~p~ to ~q~ in the clockwise direction. (Here the arc ~[p, q)~ contains ~p~ but does not contain ~q~.) If ~N~ black points are contiguous and ~N~ white points are contiguous, we can easily check the monotonicity condition. If this is not the case, the condition ~d'(b_i, b_{i+1}) \le N~ is satisfied for every ~i~. In the following, we may assume this condition is satisfied.

We shall prove that the function ~k \mapsto \sum_{i=1}^N d(w_i, b_{i+k})/2~ satisfies the monotonicity condition imposed on ~f~. We put ~g(k) = \sum_{i=1}^N (d(w_i, b_{i+k+1})-d(w_i, b_{i+k}))/2~. We need to prove that both ~\{k \mid g(k) \ge 0\}~ and ~\{k \mid g(k) \le 0\}~ are intervals. It is enough to prove that ~g~ satisfies the same monotonicity condition imposed on ~f~. We shall prove this.

We take a point ~w~ on the circle and move it. We will consider the variation of the value of ~(d(w, b_{i+k+1})-d(w, b_{i+k}))/2~. Let ~b'_{i+k}, b'_{i+k+1}~ be the antipodal points to ~b_{i+k}, b_{i+k+1}~, respectively. If we move ~w~ to the clockwise direction by a small quantity ~\Delta w~, the variation is ~-\Delta w~ if ~w~ is in the interval ~[b_{i+k}, b_{i+k+1})~, the variation is ~0~ if ~w~ is in the interval ~[b_{i+k+1}, b'_{i+k})~, the variation is ~\Delta w~ if ~w~ is in the interval ~[b'_{i+k}, b'_{i+k+1})~, the variation is ~0~ if ~w~ is in the interval ~[b'_{i+k+1}, b_{i+k})~. Hence ~h(k) = g(k+1)-g(k)~ is given by the following formula:

$$\displaystyle h(k) = \sum_{i=1}^N \left|[w_{i-1}, w_i) \cap [b_{i+k}, b_{i+k+1})\right| - \left|[w_{i-1}, w_i) \cap [b'_{i+k}, b'_{i+k+1})\right|.$$

Here ~|\cdot|~ denotes the length of an arc. For each integer ~p~ satisfying ~1 \le p \le 2N~, we define ~s_p~ so that ~b_{s_p}~ is the black point closest to the ~p~-th point (including the ~p~-th point itself) in the counterclockwise direction. Similarly, we define ~t_p~ so that ~w_{t_p}~ is the white point closest to the ~p~-th point (including the ~p~-th point itself) in the counterclockwise direction. If ~s_p~ or ~t_p~ is equal to ~N~, we replace its value by ~0~. For an integer ~p~ satisfying ~p > 2N~, we define ~s_p~, ~t_p~ by ~s_p = s_{p-2N}+N~, ~t_p = t_{p-2N}+N~. Then the above formula for ~h(k)~ gives

$$\displaystyle \begin{align*} h(k) &= \sum_{i=1}^N \left|\{1 \le p \le 2N \mid s_p \equiv i+k, t_p \equiv i-1\}\right| - \left|\{1 \le p \le 2N \mid s_{p+N} \equiv i+k, t_p \equiv i-1\}\right| \\ &= \left|\{1 \le p \le 2N \mid s_p-t_p \equiv k+1\}\right| - \left|\{1 \le p \le 2N \mid s_{p+N}-t_p \equiv k+1\}\right| \end{align*}$$

Here the congruences are modulo ~N~. This implies the function ~g(k)~ is obtained by adding the constant ~1~ on ~[s_p-t_p, s_{p+N}-t_p)~ and a constant function for each ~p~. When we show the monotonicity condition, we can ignore differences of constant functions. Therefore, it is enough to prove that the function

$$\displaystyle k \mapsto \left|\{1 \le p \le 2N \mid k \in [s_p-t_p, s_{p+N}-t_p)\}\right|$$

satisfies the monotonicity condition imposed on ~f~.

Arranging the labels of the points, we may assume that, for every ~i~, the number of black points in the interval from the first point to the ~i~-th point is greater than or equal to the number of white points in the interval from the first point to the ~i~-th point. We can achieve it in the following way. We consider the number of black points in the interval from the first point to the ~i~-th point minus the number of white points in the same interval. Take ~i~ so that this number takes the minimum. Then change the labels so that the ~i~-th point becomes the first point in the new labeling.

By definition, the values of ~s_p, t_p~ are the number of black and white points in the interval from the first point to the ~p~-th point, respectively. By the way to label the points, the inequality ~s_p-t_p \ge 0~ holds for every ~p~. Moreover, for every ~1 \le p \le N~, since ~s_{p+N} \le N~, the inequality ~s_{p+N}-t_p \le N~ holds. Since ~p \le t_{p+N}~, we have ~s_{p+2N}-t_{p+N} = N+s_p-t_{p+N} \le N+s_p-p \le N~. Therefore, for every ~1 \le p \le 2N~, we have ~s_{p+N}-t_p \le N~. Hence, for every ~1 \le p \le 2N~, we have ~0 \le s_p-t_p \le s_{p+N}-t_p \le N~. To prove the monotonicity condition, it is enough to prove that, for every ~1 \le p, q \le 2N~, the inequality ~s_q-t_q \le s_{p+N}-t_p~ holds.

For ~p, q~ satisfying ~p \le q \le p+N~, it follows from ~s_q-s_{p+N} \le 0 \le t_q-t_p~. For ~p, q~ satisfying ~p+N < q~, it follows from ~s_q-s_{p+N} \le q-(p+N) \le t_q-t_p~. For ~p, q~ satisfying ~q < p \le N~, it follows from ~s_q+t_p \le p \le s_{p+N} \le s_{p+N}+t_q~. For ~p, q~ satisfying ~q < p~ and ~p > N~, if ~p-q \le N~ is satisfied, it follows from ~s_{p+N}-s_q \ge (p+N)-q-N = p-q \ge t_p-t_q~. Finally, for ~p, q~ satisfying ~q < p~ and ~p-q > N~, if we put ~r = p-N > q~, then we have ~s_{p+N}-t_p = s_r+(N-t_p) \ge s_r \ge s_q \ge s_q-t_q~.

Therefore, for every ~1 \le p, q \le 2N~, the inequality ~s_q-t_q \le s_{p+N}-t_p~ holds, and the assertion is proved.