PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4
Setter: Prakhar Goyal
Tester: Nishank Suresh, Satyam
Editorialist: Devendra Singh
DIFFICULTY:
Easy
PREREQUISITES:
PROBLEM:
A permutation P of length N (1-based) is called good if it satisfies the following these conditions:
- For each 1 \le i \le N, P_i \neq i
- |P_1 - 1| \oplus |P_2 - 2| \oplus \ldots \oplus |P_N - N| = 0
Here, \oplus denotes the bitwise XOR operation and |X| denotes the absolute value of X.
Find any good permutation P of length N or print -1 if no such permutation exists.
Note: A permutation of length N is an array which contains every integer from 1 to N (inclusive) exactly once.
EXPLANATION:
The problem can be divided into two cases:
\textbf{Case 1}: N is even. Start with the identity permutation i.e 1, 2 ,3 ....N and now start pairing the numbers from the beginning and swapping them i.e 1 is swapped with 2, 3 is swapped with 4 and so on. The bitwise XOR of two same values is 0 and for each index i of the permutation the value of |P_i - i|=1. Therefore the XOR value calculated by |P_i - i| for each pair of adjacent values is 0.This means the total XOR is 0. Swapping ensured that for each 1 \le i \le N, P_i \neq i. Therefore this approach satisfies both the conditions.
\textbf{Case 1}: N is odd. If N=1 or N=3 the answer is -1. This can be easily checked by brute force calculation. For N=5 there exists a permutation which satisfies both these conditions which can be found easily by iterating over all permutations of length 5. For easier implementation one can use next\_permutation. Now when N \ge 5 we split the problem into two parts that is for the first 5 elements and rest N-5 elements. As N is odd, N-5 is even. So, we will use the approach mentioned in the case when N is even for the part containing N-5 elements starting from the 6 element i.e 6 is swapped with 7, 8 is swapped with 9 and so on. For first 5 elements we have already calculated the answer.
Output them together in order i.e. answer calculated for first 5 elements followed by answer for the rest N-5 elements to get the final answer.
TIME COMPLEXITY:
O(N) for each test case.
SOLUTION:
Setter's solution
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
double pi = acos(-1);
#define _time_ 1.0 * clock() / CLOCKS_PER_SEC
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define all(a) a.begin(),a.end()
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
const int maxn=1e5+5;
int solve(){
int n; // size of permutation
cin>>n;
vector<int> p(n,0);
for(int i=0 ; i<n ; i++){
p[i]=i+1; // consider the permutaion , p[i]=i (1-based index)
}
if(n%2==0){ // if n is even
for(int i=0;i<n;i+=2){
swap(p[i],p[i+1]); // swap odd indices of permutation with respective even indices
}
for(int i=0;i<n;i++){
cout<<p[i]<<" ";
}
cout<<"\n";
}
else{ // if n is odd
if(n==3 || n==1){
cout<<-1<<"\n";
}
else{ // rearranging first 5 elements as {p4, p1, p5, p2, p3}, it satisfies the given conditions.
swap(p[0],p[1]);
swap(p[0],p[3]);
swap(p[2],p[4]);
for(int i=5;i<n;i+=2){ // rearrange rest n-5 elements in the same way as done for even N;
swap(p[i],p[i+1]);
}
for(int i=0;i<n;i++){
cout<<p[i]<<" ";
}
cout<<"\n";
}
}
}
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
// freopen("input4.txt", "r", stdin);
// freopen("output4.txt", "w", stdout);
#ifdef SIEVE
sieve();
#endif
#ifdef NCR
init();
#endif
int t=1;
cin >> t;
while(t--){
solve();
}
return 0;
}
Tester-1's Solution (Python)
for _ in range(int(input())):
n = int(input())
if n%2 == 0:
for i in range(1, n, 2):
print(i+1, i, end = ' ')
else:
if n < 5:
print(-1, end = '')
else:
print('2 5 1 3 4', end = ' ')
for i in range(6, n, 2):
print(i+1, i, end = ' ')
print('')
Tester-2's Solution
#include <bits/stdc++.h>
using namespace std;
#ifndef ONLINE_JUDGE
#define debug(x) cerr<<#x<<" "; _print(x); cerr<<nline;
#else
#define debug(x);
#endif
/*
------------------------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----------------------------------
*/
int MAX=1000*1000;
int check_bin(string s){
for(auto it:s){
if((it!='0')&&(it!='1')){
return 0;
}
}
return 1;
}
int sum_cases=0;
void solve(){
int n=readIntLn(1,MAX);
sum_cases+=n;
if((n==1)||(n==3)){
cout<<"-1\n";
return;
}
int l=1;
if(n&1){
cout<<"2 3 5 1 4 "; l=6;
}
for(int i=l;i<=n;i+=2){
cout<<i+1<<" "<<i<<" ";
}
cout<<"\n";
return;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
freopen("error.txt", "w", stderr);
#endif
int test_cases=readIntLn(1,MAX);
while(test_cases--){
solve();
}
assert(getchar()==-1);
assert(sum_cases<=MAX);
return 0;
}
Editorialist's Solution
#include "bits/stdc++.h"
using namespace std;
#define ll long long
#define pb push_back
#define all(_obj) _obj.begin(),_obj.end()
#define F first
#define S second
#define pll pair<ll, ll>
#define vll vector<ll>
const int N=1e5+11,mod=1e9+7;
ll max(ll a,ll b) {return ((a>b)?a:b);}
ll min(ll a,ll b) {return ((a>b)?b:a);}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
vector<int> v(5);
bool checkpermutaion(void)
{
int x=0;
for(int i=0;i<v.size();i++)
{
x^=abs(v[i]-i-1);
if(v[i]==i+1)
return false;
}
if(x)
return false;
return true;
}
void sol(void)
{
int n;
cin>>n;
if(n==1 || n==3)
{
cout<<-1<<'\n';
return ;
}
if(n%2==0)
{
for(int i=1;i<n;i+=2)
cout<<i+1<<' '<<i<<' ';
cout<<'\n';
return ;
}
for(auto x:v)
cout<<x<<' ';
for(int i=6;i<n;i+=2)
cout<<i+1<<' '<<i<<' ';
cout<<'\n';
return ;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL),cout.tie(NULL);
for (int i = 0; i < 5; i++)
v[i] = i + 1;
bool iscorrectpermutaion = checkpermutaion();
while (next_permutation(all(v)))
{
iscorrectpermutaion = checkpermutaion();
if (iscorrectpermutaion)
break;
}
int test=1;
cin>>test;
while(test--) sol();
}