GDPERM-Editorial

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:

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 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();
}
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.