Editorial for DMOPC '21 Contest 5 P4 - 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

Note that it is not possible for there to be only one distinct difference since 1 is not prime. Thus we can conjecture that the smallest possible number of distinct differences is 2. Let's try to build a permutation that uses only the differences 2 and -3. One way of doing this is to repeat the pattern 1, 3, 5, 2, 4, 6, 8, 10, 7, 9, \dots (repeating the differences 2, 2, -3, 2, 2 periodically) which works whenever N is a multiple of 5.

Time Complexity: \mathcal{O}(N) for each test case.

Subtask 2

From here on, we will use 0-indexing for all indices and values of p_i as that will turn out to be more convenient.

Again, we can conjecture that the smallest possible number of distinct differences is 2 for all N that is not too small.

Let's find two distinct prime numbers p and q with p+q = N. By Goldbach's conjecture, we expect that such p and q will exist whenever N is even and not too small. Goldbach's conjecture is unproven and doesn't guarantee that the two primes are distinct, but it is possible to verify using a computer that such p \ne q exists for all even N between 8 and 10^6. Cases where N is small (N = 2, 4, 6) may need to be handled separately, and we can find an answer for these small N by hand and hardcode them.

Now consider setting p_i = (i \cdot p \bmod N) for all 0 \le i \le N-1. We have that p_{i+1} \equiv p_i+p \pmod N, so either p_{i+1} = p_i+p (if p_i+p < N) or p_{i+1} = p_i+p-N = p_i-q (if p_i+p \ge N) for all 0 \le i \le N-2. Hence this sequence only has two distinct adjacent differences (p and -q) as needed. Furthermore, this is a permutation since \gcd(p,N) = \gcd(p,p+q) = \gcd(p,q) = 1 (because p and q are distinct primes), and this means that if p_i = p_j, then p_i-p_j \equiv (i-j)p \equiv 0 \pmod N \implies i-j \equiv 0 \pmod N \implies i = j.

If we implement this solution by sieving all the primes up to N, then the time complexity is \mathcal{O}(N \log \log N). It is also possible to obtain \mathcal{O}(N) behaviour by trying p in increasing order and checking if p and q = N-p are both prime (in \mathcal{O}(\sqrt{N}) time for each p), as we will intuitively find a good p and q way before checking \mathcal{O}(\sqrt{N}) numbers.

Time Complexity: \mathcal{O}(N \log \log N) (or \mathcal{O}(N) behaviour) for each test case.

Subtask 3

First, we handle the small N separately, which now includes all N between 1 and 7.

If N is even, we can do the construction as in subtask 2. Note that the above construction in fact gives a cyclic sequence with only p and -q as adjacent differences (p_0-p_{N-1} = p or -q as well). Thus if N is odd, we can perform the above construction for N-1 to obtain a permutation p_0, p_1, \dots, p_{N-2} of 0, 1, \dots, N-2, cyclically shift it so that p_{N-2} = N-p-1, and set p_{N-1} = N-1 (in fact, if we use the exact same formula as shown above, we do not even need to do a cyclic shift as p_{N-2} \equiv (N-2)p \equiv -p \equiv q \pmod{N-1} \implies p_{N-2} = q = N-p-1).

Time Complexity: \mathcal{O}(N \log \log N) (or \mathcal{O}(N) behaviour) for each test case.

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

  • Goldbach's conjecture, allowing us to find primes p and q with p+q = N or p+q = N-1.
  • Coprimeness of distinct primes, allowing the sequence i \cdot p \bmod N to "cover" all residues modulo N.


There are no comments at the moment.