PROBLEM LINK:
Setter: S.Manuj Nanthan
Tester: Anshu Garg
Editorialist: Keyur Jain
DIFFICULTY
Easy
PREREQUISITES
Greatest Common Divisor
PROBLEM
You are given an integer N. Output a permutation of values from 1 to N that satisfies the following condition:
- \gcd([1+A_1,2+A_2,3+A_3,\dots,N+A_N]) > 1
It can be proven that a solution always exists. If there are multiple permutations that can satisfy the condition, then output any one of them.
As a reminder,
- A permutation of values from 1 to N is an array containing integers from 1 to N in any order but each of them appearing exactly once.
- GCD stands for Greatest Common Divisor. The greatest common divisor of a sequence is the largest integer d such that all the numbers in sequence are divisible by d. For more information, refer to here.
EXPLANATION
We need to ensure that \gcd([1+A_1,2+A_2,3+A_3,\dots,N+A_N]) > 1. Here are two simple ways to achieve this.
-
make gcd = 2 by pairing numbers with the same parity. One such solution would be [1, 2, 3, 4 \dots, N]. This makes our resulting sequence = [1 + 1, 2 + 2, 3 + 3, \dots, N + N] which has gcd = 2
-
make gcd = N + 1 by using the sequence [N, N-1, N-2 \dots, 2, 1]. This makes our resulting sequence = [1 + N, 2 + N - 1, \dots, N + 1]. This sequence has gcd = N + 1 since every element is N + 1
many more solutions are possible, but the above two are the simplest.
TIME COMPLEXITY
The time complexity is O(N)
SOLUTIONS
Setter's Solution
def inp():
return int(input())
def st():
return input().rstrip('\n')
def lis():
return list(map(int,input().split()))
def ma():
return map(int,input().split())
t=inp()
while(t):
t-=1
n=inp()
a=[i for i in range(n,0,-1)]
print(*a)
Tester's Solution
#include<bits/stdc++.h>
using namespace std ;
#define ll long long
#define pb push_back
#define all(v) v.begin(),v.end()
#define sz(a) (ll)a.size()
#define F first
#define S second
#define INF 2000000000000000000
#define popcount(x) __builtin_popcountll(x)
#define pll pair<ll,ll>
#define pii pair<int,int>
#define ld long double
const int M = 1000000007;
const int MM = 998244353;
template<typename T, typename U> static inline void amin(T &x, U y){ if(y<x) x=y; }
template<typename T, typename U> static inline void amax(T &x, U y){ if(x<y) x=y; }
#ifdef LOCAL
#define debug(...) debug_out(#__VA_ARGS__, __VA_ARGS__)
#else
#define debug(...) 2351
#endif
long long readInt(long long l,long long r,char end){
long long x = 0;
int cnt = 0;
int first =-1;
bool is_neg = false;
while(true) {
char g = getchar();
if(g == '-') {
assert(first == -1);
is_neg = true;
continue;
}
if('0' <= g && g <= '9') {
x *= 10;
x += g - '0';
if(cnt == 0) {
first = g - '0';
}
++cnt;
assert(first != 0 || cnt == 1);
assert(first != 0 || is_neg == false);
assert(!(cnt > 19 || (cnt == 19 && first > 1)));
}
else if(g == end) {
if(is_neg) {
x = -x;
}
assert(l <= x && x <= r);
return x;
}
else {
assert(false);
}
}
}
string readString(int l,int r,char end){
string ret = "";
int cnt = 0;
while(true) {
char g = getchar();
assert(g != -1);
if(g == end) {
break;
}
++cnt;
ret += g;
}
assert(l <= cnt && cnt <= r);
return ret;
}
long long readIntSp(long long l,long long r){
return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
return readString(l,r,'\n');
}
string readStringSp(int l,int r){
return readString(l,r,' ');
}
//RNG based on mersenne_twister
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
int _runtimeTerror_()
{
int N;
N = readIntLn(2,500);
vector<int> odd, even;
for(int i=1;i<=N;++i) {
if(i % 2 == 1) {
odd.push_back(i);
}
else {
even.push_back(i);
}
}
shuffle(all(odd),rng);
shuffle(all(even),rng);
for(int i=1;i<=N;++i) {
if(i % 2 == 1) {
cout << odd.back() << "\n";
odd.pop_back();
}
else {
cout << even.back() << "\n";
even.pop_back();
}
}
return 0;
}
int main()
{
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#ifdef runSieve
sieve();
#endif
#ifdef NCR
initialize();
#endif
int TESTS = 1;
//cin >> TESTS;
TESTS = readIntLn(1,500);
while(TESTS--)
_runtimeTerror_();
assert(getchar() == -1);
return 0;
}
Editorialist's Solution
static class FakeGCD {
public void solve(int testNumber, InputReader in, OutputWriter out) {
int n = in.readInt();
for (int i = 1; i <= n; i++) {
out.print(i + " ");
}
out.printLine();
}
}
Feel free to share your approach. Suggestions are welcomed as always.