Editorial for DMOPC '21 Contest 5 P4 - Permutations & Primes
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
Subtask 1
Note that it is not possible for there to be only one distinct difference since is not prime. Thus we can conjecture that the smallest possible number of distinct differences is
. Let's try to build a permutation that uses only the differences
and
. One way of doing this is to repeat the pattern
(repeating the differences
periodically) which works whenever
is a multiple of
.
Time Complexity: for each test case.
Subtask 2
From here on, we will use 0-indexing for all indices and values of as that will turn out to be more convenient.
Again, we can conjecture that the smallest possible number of distinct differences is for all
that is not too small.
Let's find two distinct prime numbers and
with
. By Goldbach's conjecture, we expect that such
and
will exist whenever
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
exists for all even
between
and
. Cases where
is small (
) may need to be handled separately, and we can find an answer for these small
by hand and hardcode them.
Now consider setting for all
. We have that
, so either
(if
) or
(if
) for all
. Hence this sequence only has two distinct adjacent differences (
and
) as needed. Furthermore, this is a permutation since
(because
and
are distinct primes), and this means that if
, then
.
If we implement this solution by sieving all the primes up to , then the time complexity is
. It is also possible to obtain
behaviour by trying
in increasing order and checking if
and
are both prime (in
time for each
), as we will intuitively find a good
and
way before checking
numbers.
Time Complexity: (or
behaviour) for each test case.
Subtask 3
First, we handle the small separately, which now includes all
between
and
.
If is even, we can do the construction as in subtask 2. Note that the above construction in fact gives a cyclic sequence with only
and
as adjacent differences (
or
as well). Thus if
is odd, we can perform the above construction for
to obtain a permutation
of
, cyclically shift it so that
, and set
(in fact, if we use the exact same formula as shown above, we do not even need to do a cyclic shift as
).
Time Complexity: (or
behaviour) for each test case.
Remark: The properties of the prime numbers this problem uses are:
- Goldbach's conjecture, allowing us to find primes
and
with
or
.
- Coprimeness of distinct primes, allowing the sequence
to "cover" all residues modulo
.
Comments