PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: raysh07
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
Simple
PREREQUISITES:
None
PROBLEM:
Given an integer N, find any permutation P such that the number of indices i with \min(P_i, P_{i+1}) being a prime number is minimized.
EXPLANATION:
Recall that other than 2, all the other prime numbers are odd.
So, a reasonable starting point is to try and ensure that every odd number is next to two smaller even numbers (greater than 2): this way, the adjacent minimums involving the odd number will both be even and hence not prime.
Working with small numbers a bit, you’ll find that the smallest odd number that can be made to do this is 7, since it can be placed between 4 and 6.
So, let’s start with [4, 7, 6] for now.
The next odd number is 9, but we also have 8 to work with now.
So, we can place 9 immediately after the 6, and then follow it with the 8.
This gives us [4, 7, 6, 9, 8].
Next is 11, and it’s easy to see that the same strategy can be followed, to obtain [4, 7, 6, 9, 8, 11, 10].
In general, we obtain a fairly straightforward pattern: start with [4, 7, 6], and then repeatedly place the next odd number followed by the next even number.
If N is odd, this will cover all numbers till N; and if N is even this will cover everything till N-1.
When N is even though, the last number in this construction will be N-2 (which is itself even), so we can just place N at the end, which won’t create any prime minimums since \min(N-2, N) = N-2 is even.
That takes care of the “large” numbers, but you might note that there are some smaller values we haven’t placed yet: namely 1, 2, 3, and 5.
Of these, 1 is a prime, while the others aren’t.
Analyzing things a bit:
- If 2 is placed next to anything other than 1, it’ll create a prime minimum.
So, ideally 2 is adjacent to only 1. - Similarly, if 3 is placed next to anything other than 1, it’ll create a prime minimum.
Once again, ideally 3 should be adjacent to only 1.
This suggests something like [2, 1, 3]. - However, both 2 and 3 have two neighbors.
We can take care of one of each using the 1, and by placing either 2 or 3 as the first element, its other neighbor is taken care of too.
However, the other neighbor remains, and there’s nothing we can do about it: we’re forced to create a minimum that’s prime (i.e. either 2 or 3). - With this in mind, let’s now try to place 5.
5 can be adjacent to 4 without creating a prime minimum, so we can just make its other neighbor either 3 or 2 (which as noted above is unavoidable anyway).
Putting this together, we have the construction
which has exactly one adjacent minimum be a prime, namely \min(P_3, P_4) = \min(3, 5) = 3.
As noted earlier it’s impossible to obtain a value of 0 since either 2 or 3 will be adjacent to something larger than them (as long as N \geq 4).
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Editorialist's code (PyPy3)
for _ in range(int(input())):
n = int(input())
if n == 2: print(1, 2)
else:
ans = [3, 1, 2]
for i in range(4, n, 2):
ans.append(i+1)
ans.append(i)
if n%2 == 0: ans.append(n)
print(*ans)