PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: iceknight1093
Tester: tabr
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
None
PROBLEM:
Given N, find a permutation of \{1, 2, \ldots, N\} such that (P_i + i) contains a 2 in its ternary representation for every i.
EXPLANATION:
There are likely several ways to approach this problem, below is one of them.
It seems somewhat hard to control the digits of the ternary representation of a sum of two numbers, but notice that there is one part of it that we can in fact control easily: the last digit.
Specifically, the last digit of the ternary representation of x is simply (x\bmod 3).
It’d be nice if we could make this last digit 2 for every (P_i + i), since that will satisfy the condition given to us.
Notice that for that to happen,
- If i \equiv 0 \pmod 3, then we need P_i \equiv 2 \pmod 3, and vice versa.
- If i \equiv 1 \pmod 3, then we need P_i \equiv 1 \pmod 3.
From now on, we work with the integers modulo 3.
The second condition is quite simple to work with: we can just choose P_i = i, for instance, and it’s automatically satisfied since a 1 matches with itself.
For the first condition, observe that we want to match a 0 to a 2 and vice versa.
The simplest way to ensure this happens would be to pair up 0's and 2's - which of course can only happen when there’s an equal number of them.
In particular, if N\equiv 0 \pmod{3} or N\equiv 1 \pmod{3}, there will in fact be an equal number of 0's and 2's, so they can be paired up and we’re done.
This leaves the case of N\equiv 2\pmod{3}, in which case it’s easy to see that we’ll have exactly one extra 2 compared to 0's (this is because the remainders modulo 3, starting from 1, are 1, 2, 0, 1, 2, 0, \ldots).
All we need to do is figure out what to do with this extra 2.
One way of dealing with it is to pair up 1 and 5, for a sum of 6 (which is \texttt{20}_{(3)} in ternary).
This uses up one 2 (from the 5) and one 1 (from the 1), and now we’re back to having an equal number of 0's and 2's so they can be paired with each other any way you like!
There are alternate solutions based on this idea as well.
For instance, another solution is to note that if you have the numbers (N-2, N-1, N), you’ll have one each of the remainders (0, 1, 2) among them.
You can pair up the remainders 0 and 2, and leave the 1 with itself - this reduces the problem to solving for N-3.
Simply repeat this process till N is small enough - say, N \leq 5, for which you can have precomputed answers (taken from the sample output, for instance).
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Tester's code (C++)
#include <bits/stdc++.h>
using namespace std;
// #define IGNORE_CR
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;
}
#ifdef IGNORE_CR
if (c == '\r') {
continue;
}
#endif
buffer.push_back((char) c);
}
}
string readOne() {
assert(pos < (int) buffer.size());
string res;
while (pos < (int) buffer.size() && buffer[pos] != ' ' && buffer[pos] != '\n') {
assert(!isspace(buffer[pos]));
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);
}
};
bool check(vector<int>& p) {
int n = (int) p.size();
for (int i = 0; i < n; i++) {
int t = p[i] + i + 1;
bool ok = false;
while (t > 0) {
if (t % 3 == 2) {
ok = true;
}
t /= 3;
}
if (!ok) {
return false;
}
}
return true;
}
int main() {
input_checker in;
int tt = in.readInt(1, 1000);
in.readEoln();
int sn = 0;
while (tt--) {
int n = in.readInt(3, 2e5);
in.readEoln();
sn += n;
vector<int> p(n);
iota(p.begin(), p.end(), 1);
auto p1 = p;
reverse(p1.begin(), p1.end());
if (check(p1)) {
p = p1;
} else {
auto p2 = p;
reverse(p2.begin() + 1, p2.end());
if (check(p2)) {
p = p2;
} else {
auto p3 = p;
reverse(p3.begin(), p3.begin() + 5);
reverse(p3.begin() + 5, p3.end());
assert(check(p3));
p = p3;
}
}
for (int i = 0; i < n; i++) {
cout << p[i] << " ";
}
cout << '\n';
}
assert(sn <= 2e5);
in.readEof();
return 0;
}
Editorialist's code (Python)
for _ in range(int(input())):
n = int(input())
p = list(range(n+1))
while n > 5:
if n%3 == 0: p[n], p[n-1] = p[n-1], p[n]
elif n%3 == 1: p[n-2], p[n-1] = p[n-1], p[n-2]
else: p[n], p[n-2] = p[n-2], p[n]
n -= 3
p[2], p[3] = p[3], p[2]
if n == 5: p[1], p[5] = 5, 1
print(*p[1:])