NPRPE - Editorial

editorial
,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: iceknight1093
Tester: mridulahi
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

None

PROBLEM:

Given a permutation P of \{1, 2, \ldots, N\}, find any permutation A also of the same integers such that P_i + A_i is not a prime for every i.

EXPLANATION:

There are many different constructions possible, here’s one of them.

If N \leq 2, no solution exists, so output -1.

For N \gt 3, a solution always exists.
One of the easiest ways to ensure that some integer is not a prime is to ensure that it’s even (and larger than 2).

Here’s one way to achieve that. Define A as follows:

  • If P_i = 1, set A_i = 3.
  • If P_i = 3, set A_i = 1.
  • Otherwise, set A_i = P_i.

That is, A is just P but with 1 and 3 swapped.
With this,

  • If P_i = 1 or P_i = 3, A_i + P_i = 4 is not prime.
  • Otherwise, P_i + A_i = 2P_i, and since P_i \gt 1 this is an even number \gt 2 and hence not prime.

We’re done!

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (Python) 
for _ in range(int(input())):
    n = int(input())
    p = list(map(int, input().split()))
    if n <= 2: print(-1)
    else:
        ans = [0]*n
        for i in range(n):
            if p[i] == 1: ans[i] = 3
            elif p[i] == 3: ans[i] = 1
            else: ans[i] = p[i]
        print(*ans)