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!)$ ~\mathcal{O}(N!)~ permutations and take the lexicographically smallest one where $i+p_i$ ~i+p_i~ is prime for all $1 \le i \le N$ ~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!)$ ~\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$ ~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$ ~N \le 10~, which hints that such a permutation exists for all $N$ ~N~.

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

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

Subtask 3

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

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

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

For the original problem, $V = 2N$ ~V = 2N~ and $E$ ~E~ is $\mathcal{O}(N^2/\ln N)$ ~\mathcal{O}(N^2/\ln N)~ as there are $\mathcal{O}(N/\ln N)$ ~\mathcal{O}(N/\ln N)~ primes under $2N$ ~2N~ by the Prime Number Theorem. Therefore, the time complexity is $\mathcal{O}(N^3/\ln N)$ ~\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)$ ~\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$ ~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$ ~i~ and greedily assign $p_i$ ~p_i~ to be the smallest valid remaining number until $i$ ~i~ is $N-300$ ~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)$ ~\mathcal{O}(N \log \log N + f(N)^3)~, where $f(N)$ ~f(N)~ is the size of the suffix of the permutation we run the lexicographically smallest matching algorithm on.

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

Comments

There are no comments at the moment.