Editorial for DMOPC '21 Contest 5 P2 - Permutations & Primes - Olympiads Online Judge

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$ ~p_1, p_2, \dots, p_N~ of $1, 2, \dots, N$ ~1, 2, \dots, N~ such that the prefix sums are not prime.

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

$N = 1$ ~N = 1~ → 1 ( $1$ ~1~ is not composite or prime)

$N = 2$ ~N = 2~ → -1

$N = 3$ ~N = 3~ → 1 3 2

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

Time Complexity: $\mathcal O(N)$ ~\mathcal O(N)~

Comments

There are no comments at the moment.