Editorial for DMOPC '21 Contest 5 P2 - 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.
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
The problem is essentially asking us to find a permutation of
such that the prefix sums are not prime.
Starting with smaller cases of , we have the following outputs:
→
1
( is not composite or prime)
→
-1
→
1 3 2
For cases where , we can use the fact that the sum of the first
natural numbers is
, which is composite if
. Proof is left as an exercise to the reader. From this, we note that if
has a permutation for
, then
also has a valid permutation, where
is just added to the end. This is because the prefix sum at
will be
.
Time Complexity:
Comments