Colourful Permutation Sorting#13027

Colourful Permutation Sorting (Editorial)

Author:

Alex Danilyuk

Let's show that it only makes sense to do shuffle for each colour at most once. Let's say that elements of permutation are written on cards, and those cards lie in numbered boxes, each box has the colour of the corresponding position. When we swap two elements, we will swap the cards and record the ids of boxes they were in. When we do the shuffle for a specific colour, we will shuffle the boxes themselves. In such an interpretation swaps and shuffles are totally independent, thus we can do all the swaps first, and then all the shuffles, now it's obvious that we don't need to shuffle the same colour twice.

If we don't use shuffles, we have to make (n - cyc) swaps, where is the number of cycles in the permutation. When we shuffle the colour, we basically say that all the positions of this colour are the same. In terms of the graph, we merge all the vertices of this colour.

Let's try all 2^{k} ways to choose which colours we will shuffle. Construct the graph of the permutation, merge the vertices of the chosen colours. The cost will be [cost for shuffles] + S(n - cyc), where is the maximum number of cycles we can split the edges of the graphs into. We can contract the vertices with indegree = outdegree = 1, so we will only have the mega-vertices corresponding to chosen colours.

Thus we have reduced our problem to the problem "Given a directed graph with at most vertices and at most edges, for each vertex indegree = outdegree, what is the maximum number of the cycles we can split the edges into?" We are aware of 2 working methods for this problem:

Common observations:

We can remove cycles one by one, the property indegree = outdegree will remain. But the order of removal can be important.

It is always optimal to take cycles of length . It is also always optimal to take cycles of length . Suppose the opposite, then in optimal solution they are in different cycles. Let's take these edges out, make a cycle out of them, and also make a cycle out of two remaining chains. It is also cycles, so it's not worse.

From here we assume that we don't have self-loops and edges in the opposite directions (if they appear during the algorithm, we remove them).

Method 1.

If there is a vertex from which there are edges to only one other vertex then all the cycles coming through this vertex will have to go through that edge, so we can contract this vertex, by glueing incoming edges with the only outcoming.

If we have at most k = 4 vertices in the graph, we can always find such a vertex, thus we have a O(k^{3}) solution.

For k = 5 vertices it is possible that each vertex has incoming and outcoming edges. Here we can remember that the total number of edges is at most , and for one edge we can bruteforce all the possibilities where cycles that go through it will go next. Then we can remove this edge and finish as before, as now there will always be a vertex we can contract.

Method 2.

It turns out that for k \le 5 it is not only optimal to take cycles of length and , but also of length , and in this order.

The reasoning is that when we are talking about cycles of length , there are already no cycles of smaller lengths in the graph. Let's recall our proof that we can take cycles of length : we supposed the opposite, took the optimal solution, took the cycles that contain the edges we want, took those edges out to form a cycle, and formed a cycle out of the chains that were remaining. We get only cycles this way, which can be less than . But let's say that L = 3 and the edges were all in different cycles in the optimal solution, otherwise we are good. Those cycles should all have a length of at least because there are no shorter cycles in the graph now. Thus the length of our "leftover" cycle is at least , which is greater than the number of vertices, thus by pigeonhole principle there will be a repeated vertex, thus we can split this cycle in at least . This is the main idea of the proof, the casework for L=4 is left to the reader.

Technically the second method is , because it just doesn't work for k > 5, but in the limitations of this problem the first method is faster, but both should pass without trouble.