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 \geq 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 \geq 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 \geq 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}$ $\frac{(N - 1) (N)}{2} + N = \frac{(N) (N + 1)}{2}$ .

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

Comments

There are no comments at the moment.