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

Subtask 1

For subtask 1, we can brute force all \mathcal{O}(N!) permutations and take the lexicographically smallest one where i+p_i is prime for all 1 \le i \le N. 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: \mathcal{O}(N \cdot N!)

Subtask 2

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

First, we can notice that such a permutation exists for all N \le 10, which hints that such a permutation exists for all N.

One key observation is that p_1 is 2 whenever N is even, which is unexpected since this means that p_1 = 1 is impossible when N is even. This happens because 2 is the only even prime number, so i+p_i is odd unless i = p_i = 1. The sum of all i+p_i for 1 \le i \le N is twice the sum of 1+2+\dots+N, which is even. If p_1 = 1, then this sum would be equal to the sum of 1 even number (for i = 1) and N-1 odd numbers (for 2 \le i \le N), which is odd for even N, giving a contradiction.

Another important observation is that after we ensure that p_1 = 2 if N is even, we can loop through i in increasing order and p_i is always the smallest number which does not appear in p_1, p_2, \dots, p_{i-1} and where i+p_i is prime (i.e. greedily choosing p_i is the correct choice) until i is around N. In fact, this means that there are many disjoint "blocks" (l,r) with p_l = r, p_{l+1} = r-1, \dots, p_r = l 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 i+p_i is not prime for some i (or if we set p_1 = 1 and N is even). By our second observation, this backtracking will only spend a significant amount of time exploring branches that do not work when i is almost N, and hence these branches are not too deep. This algorithm is fast enough to solve N \le 100 in the time limit but takes a very long time for some N \le 10^3 cases (e.g. N = 677).

Subtask 3

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

Consider the bipartite graph with N vertices labelled 1, 2, \dots, N on the left side and another N vertices labelled 1, 2, \dots, N on the right side. Add an edge between vertex u on the left and vertex v on the right if u+v 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 \mathcal{O}(VE) time for a general bipartite graph with V vertices and E edges.

First, find any perfect matching in \mathcal{O}(VE) time. Consider the vertex u labelled 1 on the left side. Either u is already matched with the smallest possible vertex, or it should be matched with a different vertex v on the right side. In the latter case, there exists an alternating cycle containing the edge between u and v. 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 u. Then such an alternating cycle corresponds to a path from u to v, so v should be the smallest labelled vertex such that v is reachable from u and there is an edge from u to v. We can find what v should be and flip the state of the edges along this alternating cycle so that u is matched with v. Now that u is matched with the smallest possible vertex v, we can delete u and v from the graph and continue to find the lexicographically smallest matching on the remaining graph. This algorithm takes \mathcal{O}(E) for each vertex, for a total of \mathcal{O}(VE) overall.

For the original problem, V = 2N and E is \mathcal{O}(N^2/\ln N) as there are \mathcal{O}(N/\ln N) primes under 2N by the Prime Number Theorem. Therefore, the time complexity is \mathcal{O}(N^3/\ln N).

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

Time Complexity: \mathcal{O}(N^3/\ln N)

Subtask 4

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 N \le 10^6 in the time limit.

Subtask 5

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

Time Complexity: \mathcal{O}(N \log \log N + f(N)^3), where f(N) is the size of the suffix of the permutation we run the lexicographically smallest matching algorithm on.

Remark 1: Intuitively, f(N) needs to be approximately the size of the prime gaps near 2N. In fact, the maximum f(N) we need for N \le 10^6 is 154, achieved when N = 674\,871. This small value allows several slower lexicographically smallest matching algorithms to pass (e.g. the \mathcal{O}(VE^2) algorithm where we try each edge e in order, running an \mathcal{O}(VE) algorithm to check from scratch if there still is a perfect matching on the remaining graph if we enforce that e 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 N, using Bertrand's Postulate and induction. The base case where N = 1 is clear. Suppose that N \ge 2 and such a permutation exists for all smaller N. Then by Bertrand's Postulate, there exists a prime P between N+1 and 2N. We can apply the induction hypothesis to find a valid permutation p_1, p_2, \dots, p_{P-N-1} of 1, 2, \dots, P-N-1 and set p_{P-N} = N, p_{P-N+1} = N-1, \dots, p_N = P-N.

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

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


There are no comments at the moment.