Subtask 1

Notice that the size of the largest set of disconnected cities is the same as the number of connected components in the graph. This subtask was created to reward efficient brute force solutions which manually calculate the number of components for each of the ~2^M~ interpretations of the king's commands. For example, one efficient method to count the number of components for a fixed set of edges is to first sort the edges in non-decreasing order of their bottom cities. Then, if the largest top city in some prefix ~1, 2, \dots, i~ of the edges is smaller than the smallest top city in some suffix ~i+1, i+2, \dots, M~, we increase the number of components by ~1~. Remember to add the number of cities with no incident edges to the final answer; these will henceforth be known as "lone" cities.

Time Complexity: ~\mathcal{O}(M2^M)~

Subtask 2

This subtask was created to reward inefficient implementations of the correct algorithm presented in subtask 4.

Time Complexity: ~\mathcal{O}(M^2)~

Subtask 3

For this subtask, notice that the number of lone cities is constant over all ~2^M~ interpretations. So, we only seek to minimize the number of components formed by the edges. For convenience of notation, let's define ~l_i := \min(a_i, b_i)~ and ~r_i := \max(a_i, b_i)~. Also, we say an edge is left-oriented if ~a_i < b_i~ and right-oriented otherwise. The first thing to notice is that if we have a pair of indices ~(i, j)~ where ~l_i < l_j~ and ~r_j < r_i~, then the ~j~-th edge is effectively useless since edges ~i~ and ~j~ will always be connected regardless of their respective orientations. After removing all useless edges, we may order the edges such that ~l_i < l_{i+1}~ and ~r_i < r_{i+1}~ for all ~i~.

At this point, we orient the edges so that all edges with an odd index are left-oriented and all edges with an even index are right-oriented. It is easy to verify that such an arrangement ensures that the two edges ~(i, i+1)~ are connected if ~r_i > l_{i+1}~, which is also the only case where it is possible to connect ~i~ and ~i+1~. Since all pairs of edges that can possibly be connected are indeed connected, this construction produces a valid interpretation for this subtask that minimizes the number of components. The diagram below provides a visual illustration of an arrangement that this algorithm may produce. Left-oriented edges are marked in red, right-oriented edges are marked in blue, and useless edges are marked in black:

Time Complexity: ~\mathcal{O}(M)~

Subtask 4

Without the constraint that each city number appears at most once, the number of lone cities may now vary based on the orientations of the edges. Let's step back for a minute and make a huge claim inspired by the solutions to the previous subtasks: If we sort the edges in non-decreasing order of their bottom cities and partition the array into as many blocks as possible ~[L_1, R_1], [L_2, R_2], \dots, [L_k, R_k]~ such that the largest top city up to index ~R_i~ is no greater than the smallest top city from ~L_{i+1}~ onwards for all ~1 \le i < k~, then each block of edges can be oriented in a manner such that the entire block is connected and no city has two incident edges (i.e. the number of lone cities is strictly minimized). Note that for any ~i~ where the largest top city up to index ~R_i~ is equal to the smallest top city from ~L_{i+1}~ onwards, say ~x~, then one of the cities at ~x~ could have two incident edges. However, if we flip the orientation of all edges from block ~1~ to block ~i~ we will increase the number of components by ~1~ and decrease the number of lone cities by ~1~, leaving the overall answer unchanged. Repeating this process, we see that the claim really suggests that there is some optimal arrangement where the number of lone cities is globally minimized (equal to ~2N - 2M~). If this claim holds true then any arrangement of this form is clearly optimal, as it both minimizes the number of components as well as the number of lone cities. Now, let's back our claim up by construction.

First of all, to ensure that no city has two incident edges, edges sharing an endpoint must be arranged so that both cities at that endpoint are connected to an edge. In particular, this means the orientation of one of these edges uniquely determines the other. Since each city number appears at most twice, the only implication structures that may appear are chains and cycles. Let us only focus on chains first. In fact, let's start off by assuming all of the implications in the graph are chains where ~r_i = l_{i+1}~ (simple, increasing chains). For each chain, let its left and right endpoints be ~x_i~ and ~y_i~ respectively. It is easy to see that different chains will have different ~x_i~ and ~y_i~, so the set of ~x_i~'s and ~y_i~'s is once again unique. This should motivate us to return to the construction provided in the previous subtask, except we now work with chains of edges instead of just the edges themselves. One thing that is important to note is that none of the chains are "useless" anymore; chains ~(i, j)~ with ~x_i < x_j~ and ~y_j < y_i~ must have opposite orientations, or we risk having a suboptimal arrangement. For example, another diagram is provided below to illustrate a possible arrangement this algorithm produces, this time using different colours to denote different chains (orientations should be self-evident at this point):

Intuitively, the construction works because any intersection of chains is always optimally oriented in opposite orientations. It should be clear that two overlapping chains with the same orientation can never produce a better answer than the same two chains with opposite orientations. To arrive at a more rigorous proof, we may consider the connection point shared between two adjacent edges in the same chain. If no chain crosses through this point then the left and right portions will be disconnected, which is consistent with our claim because the two edges of the chain would reside in different blocks. Otherwise, if there exist some edges that cross over the connection point, they must be from a different chain. By construction, at least one of these chains will have the opposite orientation, thus "stringing" the two edges together and merging them into a single component. This is once again consistent with our previous claim, as it reflects the case where these edges belong to the same block.

Returning back to the task at hand, we have still yet to consider chains with more complex patterns and cycles. Luckily, these do not serve as too much of an extra obstacle. A chain that reverses back on itself can be simplified and viewed as just a single edge, as it accepts a superset of the connections that the single edge accepts:

In a similar fashion, cycles are even nicer to work with; they simplify into two chains sharing the same endpoints that are left-oriented and right-oriented at the same time, which means that we can simply select their orientation arbitrarily! Any complex chains and cycles can be simplified and treated as simple chains, so our solution extends naturally to the general case.

Time Complexity: ~\mathcal{O}(M)~

Remarks:

• The problem was initially written as merely subtask 3, serving as a mid-level fourth problem in an average DMOPC problemset. However, when attempting to simplify the input from ~4M~ total cities to ~2M~ total cities, I ran into issues with cases where some cities are mentioned more than once. In fact, the first case which I struggled with for the longest is included as the fifth case of the first batch, containing edges ~(1, 4), (2, 4), (2, 3), (3, 5)~. After a few days of struggling with the generalized version, I eventually found the solution presented above after imposing the extra constraint that no city number appears more than twice. What seemed like just a tiny tweak in the constraints surprisingly managed to elevate the problem into becoming one of the hardest DMOPC problems in recent history.
• The fully generalized version (that is, without the constraint on the frequency of each city) remains unsolved in polynomial time, and is still very much an open-ended problem. If you have made any progress on it, I would love to discuss the problem with you in the comments section below.