Editorial for DMOPC '21 Contest 5 P6 - Permutations & Primes

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: zhouzixiang2004

For subtask 1, we can brute force all permutations and take the lexicographically smallest one where is prime for all . One way of doing this is with next_permutation in C++ and breaking as soon as we find a valid permutation since next_permutation iterates through all permutations in lexicographical order.

Time Complexity:

For subtask 2, we need to make some observations, which may be easier to notice if we print out the answers for found by a brute force and look for patterns.

First, we can notice that such a permutation exists for all , which hints that such a permutation exists for all .

One key observation is that is whenever is even, which is unexpected since this means that is impossible when is even. This happens because is the only even prime number, so is odd unless . The sum of all for is twice the sum of , which is even. If , then this sum would be equal to the sum of even number (for ) and odd numbers (for ), which is odd for even , giving a contradiction.

Another important observation is that after we ensure that if is even, we can loop through in increasing order and is always the smallest number which does not appear in and where is prime (i.e. greedily choosing is the correct choice) until is around . In fact, this means that there are many disjoint "blocks" with that form a prefix of the lexicographically smallest permutation. Intuitively, this happens because prime numbers behave like random numbers and the gaps between them are not too large.

One way to combine these observations to solve subtask 2 is to use recursive backtracking, iterating through the permutations in lexicographical order and backtracking as soon as is not prime for some (or if we set and is even). By our second observation, this backtracking will only spend a significant amount of time exploring branches that do not work when is almost , and hence these branches are not too deep. This algorithm is fast enough to solve in the time limit but takes a very long time for some cases (e.g. ).

For subtask 3, we need a better way of thinking about the problem.

Consider the bipartite graph with vertices labelled on the left side and another vertices labelled on the right side. Add an edge between vertex on the left and vertex on the right if is prime. We can model a permutation as a perfect matching on this graph.

Thus, the problem is equivalent to finding the lexicographically smallest matching in this graph. We now describe an algorithm that takes time for a general bipartite graph with vertices and edges.

First, find any perfect matching in time. Consider the vertex labelled on the left side. Either is already matched with the smallest possible vertex, or it should be matched with a different vertex on the right side. In the latter case, there exists an alternating cycle containing the edge between and . Consider directing each edge of the graph from left to right if it is in the matching and right to left if it is not, and doing a depth-first search from . Then such an alternating cycle corresponds to a path from to , so should be the smallest labelled vertex such that is reachable from and there is an edge from to . We can find what should be and flip the state of the edges along this alternating cycle so that is matched with . Now that is matched with the smallest possible vertex , we can delete and from the graph and continue to find the lexicographically smallest matching on the remaining graph. This algorithm takes for each vertex, for a total of overall.

For the original problem, and is as there are primes under by the Prime Number Theorem. Therefore, the time complexity is .

Slower lexicographically smallest matching algorithms may pass too if they are fast in practice.

Time Complexity:

Subtask 4 is created to reward solutions that combine a few observations in subtask 2 with the bipartite matching modelling in subtask 3 but are too slow to solve in the time limit.

For subtask 5, we can combine the observations in subtask 2 with the bipartite matching modelling in subtask 3. We can iterate through and greedily assign to be the smallest valid remaining number until is or so, and then run the subtask 3 algorithm on the remaining graph.

Time Complexity: , where is the size of the suffix of the permutation we run the lexicographically smallest matching algorithm on.

Remark 1: Intuitively, needs to be approximately the size of the prime gaps near . In fact, the maximum we need for is , achieved when . This small value allows several slower lexicographically smallest matching algorithms to pass (e.g. the algorithm where we try each edge in order, running an algorithm to check from scratch if there still is a perfect matching on the remaining graph if we enforce that is in the matching) as they run fast in practice.

Remark 2: It is possible to prove with elementary methods that such a permutation exists for all , using Bertrand's Postulate and induction. The base case where is clear. Suppose that and such a permutation exists for all smaller . Then by Bertrand's Postulate, there exists a prime between and . We can apply the induction hypothesis to find a valid permutation of and set .

Remark 3: The properties of the prime numbers this problem uses are:

• Parity, causing the unexpected fact that for even .
• Small prime gaps/random prime distribution, causing to greedily be the smallest valid number until is almost .
• Bertrand's Postulate, allowing us to prove that such a permutation exists for all .