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.

Author: uselessleaf

The problem is essentially asking us to find a permutation p_1, p_2, \dots, p_N of 1, 2, \dots, N such that the prefix sums are not prime.

Starting with smaller cases of N, we have the following outputs:

N = 11 (1 is not composite or prime)

N = 2-1

N = 31 3 2

For cases where N \ge 4, we can use the fact that the sum of the first N natural numbers is \frac{(N)(N+1)}{2}, which is composite if N \ge 3. Proof is left as an exercise to the reader. From this, we note that if N-1 has a permutation for N \ge 4, then N also has a valid permutation, where N is just added to the end. This is because the prefix sum at N will be \frac{(N-1)(N)}{2}+N = \frac{(N)(N+1)}{2}.

Time Complexity: \mathcal O(N)


There are no comments at the moment.