FAKEGCD - EDITORIAL

editorial
, ,
1

PROBLEM LINK:

Contest
Practice

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. :slight_smile:

2 Likes