PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: notsoloud
Tester: tabr
Editorialist: iceknight1093
DIFFICULTY:
1928
PREREQUISITES:
Observation
PROBLEM:
Given N, construct a permutation of \{1, 2, \ldots, N\} such that |P_i - i| is a prime for every i, or claim that non exist.
EXPLANATION:
Let’s first try to solve the problem for small values of N.
If N \leq 3, no solution exists.
Otherwise, you can either work out by hand or run a brute-force across all N! permutations, and note that an answer does exist for N = 4, 5, 6, 7. For example:
- [3, 4, 1, 2] for N = 4
- [3, 4, 5, 1, 2] for N = 5
- [3, 4, 5, 6, 2, 1] for N = 6
- [3, 4, 5, 6, 7, 1, 2] for N = 7
In fact, this is already enough to solve the entire problem!
Notice that if a valid permutation of length N exists, then a valid permutation of length N+4 exists as well.
The idea for this comes from the solution for N = 4: pair up (N+1, N+3) and (N+2, N+4), and then using the solution we already have for the first N elements.
That is, set:
- P_{N+3} = N+1
- P_{N+4} = N+2
- P_{N+1} = N+3
- P_{N+2} = N+4
For each of these indices, the difference between i and P_i is 2, which is indeed a prime; so they’re taken care of.
By continually extending by 4 in this fashion, we obtain a solution for any N \geq 4.
As an example, a solution for N = 13 would look as follows:
- Start with N = 5, and P = [3, 4, 5, 1, 2]
- Add in the next 4 elements using the above strategy, to obtain P = [3, 4, 5, 1, 2, \underline{8, 9, 6, 7}]
- Once again add in the next 4 elements, to obtain P = [3, 4, 5, 1, 2, 8, 9, 6, 7, \underline{12, 13, 10, 11}]
This is the final permutation we’re looking for.
TIME COMPLEXITY
\mathcal{O}(N) per testcase.
CODE:
Tester's code (C++)
#include <bits/stdc++.h>
using namespace std;
struct input_checker {
string buffer;
int pos;
const string all = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
const string number = "0123456789";
const string upper = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const string lower = "abcdefghijklmnopqrstuvwxyz";
input_checker() {
pos = 0;
while (true) {
int c = cin.get();
if (c == -1) {
break;
}
buffer.push_back((char) c);
}
}
string readOne() {
assert(pos < (int) buffer.size());
string res;
while (pos < (int) buffer.size() && buffer[pos] != ' ' && buffer[pos] != '\n') {
res += buffer[pos];
pos++;
}
return res;
}
string readString(int min_len, int max_len, const string& pattern = "") {
assert(min_len <= max_len);
string res = readOne();
assert(min_len <= (int) res.size());
assert((int) res.size() <= max_len);
for (int i = 0; i < (int) res.size(); i++) {
assert(pattern.empty() || pattern.find(res[i]) != string::npos);
}
return res;
}
int readInt(int min_val, int max_val) {
assert(min_val <= max_val);
int res = stoi(readOne());
assert(min_val <= res);
assert(res <= max_val);
return res;
}
long long readLong(long long min_val, long long max_val) {
assert(min_val <= max_val);
long long res = stoll(readOne());
assert(min_val <= res);
assert(res <= max_val);
return res;
}
vector<int> readInts(int size, int min_val, int max_val) {
assert(min_val <= max_val);
vector<int> res(size);
for (int i = 0; i < size; i++) {
res[i] = readInt(min_val, max_val);
if (i != size - 1) {
readSpace();
}
}
return res;
}
vector<long long> readLongs(int size, long long min_val, long long max_val) {
assert(min_val <= max_val);
vector<long long> res(size);
for (int i = 0; i < size; i++) {
res[i] = readLong(min_val, max_val);
if (i != size - 1) {
readSpace();
}
}
return res;
}
void readSpace() {
assert((int) buffer.size() > pos);
assert(buffer[pos] == ' ');
pos++;
}
void readEoln() {
assert((int) buffer.size() > pos);
assert(buffer[pos] == '\n');
pos++;
}
void readEof() {
assert((int) buffer.size() == pos);
}
};
int main() {
input_checker in;
int tt = in.readInt(1, 1000);
in.readEoln();
vector<vector<int>> a(8);
for (int n = 4; n <= 7; n++) {
vector<int> p(n);
iota(p.begin(), p.end(), 0);
do {
int ok = 1;
for (int i = 0; i < n; i++) {
int t = abs(i - p[i]);
if (t == 2 || t == 3 || t == 5) {
} else {
ok = 0;
}
}
if (ok) {
a[n] = p;
break;
}
} while (next_permutation(p.begin(), p.end()));
}
int sn = 0;
while (tt--) {
int n = in.readInt(2, 1e5);
in.readEoln();
sn += n;
if (n <= 3) {
cout << -1 << " \n";
} else {
vector<int> ans;
while (n - (int) ans.size() >= 8) {
int t = (int) ans.size() + 1;
for (int i = 0; i < 4; i++) {
ans.emplace_back(a[4][i] + t);
}
}
int s = n - (int) ans.size();
int t = (int) ans.size() + 1;
// cerr << s << " " << t << endl;
for (int i = 0; i < s; i++) {
ans.emplace_back(a[s][i] + t);
}
for (int i = 0; i < n; i++) {
cout << ans[i] << " ";
}
cout << '\n';
for (int i = 0; i < n; i++) {
int t = abs(ans[i] - i - 1);
assert(t == 2 || t == 3 || t == 5);
}
sort(ans.begin(), ans.end());
for (int i = 0; i < n; i++) {
assert(ans[i] == i + 1);
}
}
}
cerr << sn << endl;
assert(sn <= 1e6);
in.readEof();
return 0;
}
Editorialist's code (Python)
saved = [ [3, 4, 1, 2], [3, 4, 5, 1, 2], [3, 4, 5, 6, 2, 1], [3, 4, 5, 6, 7, 1, 2] ]
for _ in range(int(input())):
n = int(input())
if n <= 3: print(-1)
else:
ans = [0]*(n+1)
while n > 7:
ans[n], ans[n-2] = n-2, n
ans[n-1], ans[n-3] = n-3, n-1
n -= 4
ans[1:n+1] = saved[n-4]
print(*ans[1:])