# GDPERM-Editorial

Setter: Prakhar Goyal
Tester: Nishank Suresh, Satyam
Editorialist: Devendra Singh

Easy

# PREREQUISITES:

bitwise XOR operation

# 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 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){
}
long long readIntLn(long long l,long long 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(){
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
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);}
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();
}
``````
2 Likes

Could anyone please explain why my solution was showing TLE for some test cases. It is written that the sum over all test cases will not exceed 10^6 and my solutionâ€™s TimeComplexity is O(N) but still it was showing TLE for some cases. Is this just because I am using JAVA Language (is it a language specific problem?) and if it is what should I do so that I do not face this issue again?
I know my solution is wrong as I have not considered the cases when n is odd, I have just printed -1 for odd test cases. I just want to know why it was showing TLE.
My Code :-

/* package codechef; // donâ€™t place package name! */

import java.util.;
import java.lang.
;
import java.io.*;

/* Name of the class has to be â€śMainâ€ť only if the class is public. */
class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
try{
Scanner obj = new Scanner(System.in);
int t = obj.nextInt();
while (t > 0)
{
tâ€“;
int n = obj.nextInt();
if (n % 2 != 0)
{
System.out.println("-1");
continue;
}
int arr[] = new int[n];
int i, j = 0;
for (i=0;i<n;i++)
{
j = i + 1;
if (j % 2 == 0)
{
arr[i] = j - 1;
}
else
{
arr[i] = j + 1;
}
}
for (i=0;i<n;i++)
{
System.out.print(arr[i] + " ");
}
System.out.println();
}
}catch(Exception e){
return;
}
}
}

Its better to give the link to your submission than pasting the code

I have run my code using generators,there is no testcase for which it is giving WA, kindly just tell me ,where my code is failing Solution: 62898691 | CodeChef
@devendra7700 ,
What are those 3 testcases

N <= 10^6 . So why I am getting TLE in O(n) approach?

can somebody explain why here -1 is printed for N=3?
When there exists an array [2, 3, 1].

why my java code is showing TLE when my approach is correct and time complexity is O(N)
import java.util.;
import java.lang.
;
import java.io.*;

/* Name of the class has to be â€śMainâ€ť only if the class is public. */
class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
Scanner sc=new Scanner(System.in);
int t=sc.nextInt();
while(tâ€“>0){
int n=sc.nextInt();
if(n==1 || n==3)
System.out.println(-1);
else {
if(n%2==0){
for(int i=n;i>=1;iâ€“){
System.out.print(i+" â€ś);
}
System.out.println();
}
else{
System.out.print(3+â€ť â€ś+5+â€ť â€ś+1+â€ť â€ś+2+â€ť â€ś+4+â€ť â€ś);
for(int i=n;i>=6;iâ€“){
System.out.print(i+â€ť ");
}
System.out.println();
}
}
}
}

}

Hi, my observation for N even was that inverted identity permutation gives symmetric xor operations from both ends of the array, so the middle one will be x XOR x = 0.

So in general, c++ allows 10^6 operations per second and you can consider java solutions to run at 70 % speed of what c++ offers .Here what you are doing is first storing it in an array and then printing it again this would require 2*10^6 operations in worst case so try to directly print the solution in some way or the other.That will run in 10^6 and might not give tle . you can read this comment Number of Operations in 1 second ? - Codeforces by an LGM for better explanation .

1 Like

Hi, the problem is that Java `println` operation is quite slow, and your code calls it a lot of times. My workaround was to build the result string with StringBuilder and then `System.out.println()` only once.

Here we have to satisfy 2 conditions, the first condition is okay when [2,3,1]. But when checking the second condition the output will be 1^1^2 = 0^2 = 2, which is not equal to 0, as required by the second condition.