PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Authors: Chaithanya Shyam D
Testers: Abhinav Sharma and Lavish Gupta
Editorialist: Nishank Suresh
DIFFICULTY:
Simple
PREREQUISITES:
None
PROBLEM:
Given N, construct a permutation P of the integers \{1, 2, 3, \ldots, N\} such that i does not divide P_i for each 2 \leq i \leq N.
EXPLANATION:
One possible solution is to simply take the identity permutation P which has P_i = i for every i, and then rotate it right by one step.
This gives the permutation P = [N, 1, 2, 3, \ldots, N-1], which is a valid answer for every N.
Why?
For every 2 \leq i \leq N, we have P_i = i-1.
i does not divide i-1 for any integer i \geq 2 so this permutation is valid.
TIME COMPLEXITY:
\mathcal{O}(N) per test case.
SOLUTIONS:
Tester's Solution (C++)
#include <bits/stdc++.h>
using namespace std;
#define ll long long
/*
------------------------Input Checker----------------------------------
*/
long long readInt(long long l,long long r,char endd){
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true){
char g=getchar();
if(g=='-'){
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g && g<='9'){
x*=10;
x+=g-'0';
if(cnt==0){
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);
assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd){
if(is_neg){
x= -x;
}
if(!(l <= x && x <= r))
{
cerr << l << ' ' << r << ' ' << x << '\n';
assert(1 == 0);
}
return x;
} else {
assert(false);
}
}
}
string readString(int l,int r,char endd){
string ret="";
int cnt=0;
while(true){
char g=getchar();
assert(g!=-1);
if(g==endd){
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,' ');
}
/*
------------------------Main code starts here----------------------------------
*/
const int MAX_T = 600;
const int MAX_N = 100000;
const int MAX_SUM_N = 200000;
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
int sum_n = 0;
int max_n = 0;
int yess = 0;
int nos = 0;
int total_ops = 0;
ll z = 998244353;
void solve()
{
int n = readIntLn(2 , MAX_N) ;
sum_n += n ;
for(int i = 1 ; i < n ; i++)
{
cout << i+1 << ' ';
}
cout << 1 << endl ;
return ;
}
signed main()
{
//fast;
#ifndef ONLINE_JUDGE
freopen("inputf.txt" , "r" , stdin) ;
freopen("outputf.txt" , "w" , stdout) ;
freopen("error.txt" , "w" , stderr) ;
#endif
int t = 1;
t = readIntLn(1,MAX_T);
for(int i=1;i<=t;i++)
{
solve() ;
}
assert(getchar() == -1);
assert(sum_n <= MAX_SUM_N);
cerr<<"SUCCESS\n";
cerr<<"Tests : " << t << '\n';
cerr<<"Sum of lengths : " << sum_n << '\n';
// cerr<<"Maximum length : " << max_n << '\n';
// cerr<<"Total operations : " << total_ops << '\n';
// cerr<<"Answered yes : " << yess << '\n';
// cerr<<"Answered no : " << nos << '\n';
}
Editorialist's Solution (Python)
for _ in range(int(input())):
n = int(input())
print(str(n) + ' ' + ' '.join(str(i) for i in range(1, n)))