 # XORPERM - Editorial

Setter: TheScrasse
Preparer: Nandeesh Gupta
Tester: Harris Leung
Editorialist: Trung Dang

1482

None

# PROBLEM:

Given N, it is required to find a permutation p of numbers 1, 2, …, N such that:

• p_i \oplus p_{i+1} \neq p_{i+2} \text{ , where } 1 \leq i \leq N-2

(Note: \oplus denotes the XOR operation between two values)

Print the Permutation if such a sequence exists. There may be more than one such permutations. It is sufficient to find any one.

# EXPLANATION:

Sample input let us know that for N = 3, we cannot construct such a permutation. We shall prove that there is a construction that works for every N \ge 4.

Let’s consider the simplest permutation possible: [1, 2, 3, \dots, N]. Observe that except from [1, 2, 3] which forms a bad triple, every triple after that is good (i.e. for every i \ge 3, we have i \oplus (i + 1) \neq (i + 2)).

Quick proof: i and i + 1 have the same most significant bit most of the time, which makes i \oplus (i + 1) < i (since the XOR will make this most significant bit disappear). The only case that this is not the case is when i = 2^k - 1 for some integer k, and we can prove that only k = 1 makes i \oplus (i + 1) = i + 2.

Therefore, the idea is to slightly modify this simplest permutation so that 1, 2, and 3 are not consecutive, while still maintaining the “consecutive” structure of the remaining values. One possible way is to replace [1, 2, 3, 4] with [1, 3, 4, 2], then proceed increasingly from 5 (we can easily prove that this works by showing that 4 \oplus 2 \ne 5 and 2 \oplus 5 \ne 6).

# TIME COMPLEXITY:

Time complexity is O(N) for each test case.

# SOLUTION:

Preparer's Solution
#include<iostream>
#include<cassert>

int main(){
int t; std::cin>>t; while(t--){
int n; std::cin>>n;
assert(n>=3);
if(n==3) std::cout<<-1;
else{
std::cout<<"1 3 4 2";
for(int i=5; i<=n; ++i)
std::cout<<" "<<i;
}
std::cout<<'\n';
}
return 0;
}

Tester's Solution
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fi first
#define se second
int n;
void solve(){
cin >> n;
if(n==3){
cout << "-1\n";return;
}
cout << 2 << ' ';
for(int i=n; i>=1 ;i--){
if(i!=2) cout << i << ' ';
}
cout << '\n';
}
int main(){
ios::sync_with_stdio(false);cin.tie(0);
int t;cin >> t;while(t--) solve();
}

Editorialist's Solution
#include <bits/stdc++.h>
using namespace std;

int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int t; cin >> t;
while (t--) {
int n; cin >> n;
if (n == 3) {
cout << "-1\n";
} else {
cout << "1 3 4 2 ";
for (int i = 5; i <= n; i++) {
cout << i << " ";
}
cout << '\n';
}
}
}


Can someone tell me which test case is not getting passed?

for _ in range(int(input())):
n = int(input())
if n==3:
print(-1)
if n==4:
print(1,2,4,3)
if n==5:
print(5,1,2,4,3)
if n==6:
print(6,5,1,2,4,3)
if n==7:
print(7 , 6, 5, 1, 2, 4, 3)
elif n > 8:
powers = [1,2,4, 5, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536]
ans = []
ind = 0
for i in range(1,n+1):
if i in powers:
ind+=1
continue
ans.append(i)
ans.extend(powers[1:ind])
ans.append(1)
print(*ans)


if you submit and get wrong answer, you will see an option to debug, where you will be shown the smallest test case for which your code does not pass.

I am unable to select debug option, it is saying that this problem is not available to debug

Oh, sorry, I didn’t think about that. I guess for constructive problems that feature is not available Ok, so is there no way on knowing which test case is failing for my code?

If a problem says “if there are multiple answers, print any,” you will not be able to auto debug. Otherwise, you should be able to.

Try this test case

1
8


You have not handled the case when n==8.

1 Like

For n=8

1 Like

Yes, now its passing all the test cases, thank you