Subtask 1

Ignore the paths which don't cross the river (i.e., compute them separately).

Also, ignore the length of the bridge (i.e., compute it separately).

It can be proved that the solution is optimal when the bridge is built at one of the positions ~S_i~ or ~T_i~. Therefore, we can choose the position by brute force. The complexity will be ~\mathcal O(N^2)~.

Subtask 2

If we build a bridge at position ~X~, then ~D_i~ (driving distance of citizen ~i~) will be ~|X-S_1|+|X-T_1|~. The total sum is ~S = |X-S_1|+|X-T_1|+\dots+|X-S_N|+|X-T_N|~.

Sort ~\{S_1, T_1, \dots, S_N, T_N\}~ in non-decreasing order, and let the sorted sequence be ~\{x_1, x_2, \dots, x_{2N}\}~. Then, ~S = |X-x_1|+|X-x_2|+\dots+|X-x_{2N}|~.

It can be proved that ~S~ is minimized when ~x_N \le X \le X_{N+1}~. Then, ~S~ will be ~x_{2N}+x_{2N-1}+\dots+x_{N+1}-x_N-\dots-x_2-x_1~.

The complexity of this solution is ~\mathcal O(N \log N)~.

Subtask 3

Similar to Subtask 1, it can be proved that the solution is optimal when the bridge is built at two of the positions ~S_i~ or ~T_i~. Therefore, we can choose the positions by brute force. The complexity will be ~\mathcal O(N^3)~.

Subtask 4

Suppose we build two bridges at positions ~L~ and ~R~ (wlog ~L < R~).

For a particular citizen ~i~, let ~P_s = \min(S_i, T_i)~ and ~P_e = \max(S_i, T_i)~. Note that we only consider citizen who has to cross the river to go from home to the office. ~(P_s, P_e)~ now can be considered an interval.

For a given interval ~(P_s, P_e)~ (again wlog ~P_s < P_e~), how do we determine which bridge to use? We can only use bridge ~L~ iff

$$\displaystyle |P_s-L|+|P_e-L| < |P_s-R|+|P_e-R| \tag{1}$$

(If they are equal, we can use either bridge).

Using Equation 1, we will now prove the following

Lemma 0.0.1. It is optimal to use the bridge at ~L~ if

$$\displaystyle P_s+P_e < L+R \tag{2}$$

And it is optimal to use the bridge at ~R~ if

$$\displaystyle P_s+P_e > L+R \tag{3}$$

Note that this does not imply the inverse. That is, optimality of using bridge at ~L~ or ~R~ does not imply the equations.

Proof. To prove Lemma 0.0.1, we need to prove that we can derive Equation 1 from Equation 3. We do so case by case. Denote the interval ~(P_s, P_e)~ with

|---------|

Case 1

|---------| L R

That is, we have ~P_e \le L~. In this case, Equation 1 expands to

$$\displaystyle \begin{align*} |P_s-L|+|P_e-L| &< |P_s-R|+|P_e-R| \\ 2L-(P_s+P_e) &< 2R-(P_s-P_e) \\ 2L &< 2R \end{align*}$$

Which is always true. So, we need to prove that in this case, ~P_s+P_e < L+R~ always holds. Since we have ~P_e \le L~:

$$\displaystyle \begin{align*} P_s+P_e &\le P_e+P_e \quad &&\text{Since }P_s \le P_e \\ &\le 2L \quad &&\text{Since }P_e \le L \\ &< L+R \quad &&\text{Since }L < R \end{align*}$$

Case 2

L R |---------|

That is, we have ~P_s \ge R~. We prove similar to Case 1. Equation 1 expands to

$$\displaystyle \begin{align*} |P_s-L|+|P_e-L| &< |P_s-R|+|P_e-R| \\ (P_s+P_e)-2L &< (P_s-P_e)-2R \\ 2L &> 2R \end{align*}$$

Which is always false. So, we need to prove that in this case, ~P_s+P_e < L+R~ never holds. Since we have ~P_s \ge R~:

$$\displaystyle \begin{align*} P_s+P_e &\ge P_s+P_s \quad &&\text{Since }P_s \le P_e \\ &\ge 2R \quad &&\text{Since }P_s \ge R \\ &> L+R \quad &&\text{Since }L < R \end{align*}$$

Case 3

  |---------|
L        R

Thus, we have ~L \le P_s \le R \le P_e~. Equation 1 expands to

$$\displaystyle \begin{align*} |P_s-L|+|P_e-L| &< |P_s-R|+|P_e-R| \\ (P_s+P_e)-2L &< R-P_s+P_e-R \\ (P_s+P_e)-2L &< P_e-P_s \\ 2P_s &< 2L \end{align*}$$

Which is always false. So, we need to prove that in this case, ~P_s+P_e < L+R~ never holds:

$$\displaystyle \begin{align*} P_s+P_e &\ge L+P_e \quad &&\text{Since }L \le P_s \\ &\ge L+R \quad &&\text{Since }R \le P_e \end{align*}$$

Case 4

|---------|
   L        R

Thus, we have ~P_s \le L \le P_e \le R~. Equation 1 expands to

$$\displaystyle \begin{align*} |P_s-L|+|P_e-L| &< |P_s-R|+|P_e-R| \\ L-P_s+P_e-L &< 2R-P_s-P_e \\ 2P_e &< 2R \end{align*}$$

Which is always true. So, we need to prove that in this case, ~P_s+P_e < L+R~ always holds:

$$\displaystyle \begin{align*} P_s+P_e &\le L+P_e \quad &&\text{Since }P_s \le L \\ &\le L+R \quad &&\text{Since }P_e \le R \end{align*}$$

Case 5

|---------|
   L   R

Thus, we have ~P_s \le L \le R \le P_e~. Equation 1 expands to

$$\displaystyle \begin{align*} |P_s-L|+|P_e-L| &< |P_s-R|+|P_e-R| \\ L-P_s+P_e-L &< R-P_s+P_e-R \\ 0 &< 0 \end{align*}$$

Which is always false, and in particular, it implies that the distance of using either of the bridges is the same. Thus, using any of the two bridges is always optimal.

Case 6

  |---------|
L             R

Thus, we have ~L \le P_s \le P_e \le R~. From Equation 3:

$$\displaystyle \begin{align*} P_s+P_e &< L+R \\ 2(P_s+P_e) &< 2L+2R \\ (P_s+P_e)-2L &< 2R-(P_s+P_e) \\ |P_s-L|+|P_e-L| &< |P_s-R|+|P_e-R| \end{align*}$$

Which is equation 1. □

Thus, there exists a way to separate the intervals into those which should go to the left bridge and those which should go to the right bridge. Sort the intervals by ~P_s+P_e~, and for every possible separation of this sequence of intervals, try to find the optimal placement of two bridges.

The optimal placement of a partition can be solved using the algorithm in Subtask 2. So, the total complexity is ~\mathcal O(N^2 \log N)~.

Subtask 5

One way to do this in ~\mathcal O(N \log^2 N)~: we keep track of a data structure to count the cost of placing a bridge in each possible position (initially, all are zero). We add the intervals one by one. When we add an interval ~(P_s, P_e)~, we are actually adding to each position ~x~, ~|P_s-x|~ and ~|P_e-x|~. ~f(x) = |A-x|~, though, is convex, so the sum over all these convex functions is a convex function. So we can ternary search over the sum of these convex functions to find the minimum in ~\mathcal O(\log^2 N)~ time.

There is another solution in ~\mathcal O(N \log N)~. Note that the optimal location of a bridge in each prefix is between the medians of the positions. So, the problem reduces to finding medians of each prefix. This incremental medians problem can be solved by using two heaps: one min-heap, and one max-heap. When we add an interval, we add ~P_s~ and ~P_e~ in the heaps in such a way that both heaps contain equal number of elements (possibly transferring elements between heaps). Then, the medians can be found in ~\mathcal O(1)~.