Editorial for DMOPC '21 Contest 5 P6 - Permutations & Primes
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
Subtask 1
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:
Subtask 2
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.
).
Subtask 3
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
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.
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 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
.
Comments