PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4
Setter: TheScrasse
Preparer: Nandeesh Gupta
Tester: Harris Leung
Editorialist: Trung Dang
DIFFICULTY:
1482
PREREQUISITES:
None
PROBLEM:
Chef has received a challenge for which he needs your help.
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)
Please help the Chef in identifying a valid permutation as described above.
Print the Permutation if such a sequence exists. There may be more than one such permutations. It is sufficient to find any one.
If no such sequence exists, please print -1 as the answer.
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';
}
}
}
