PROBLEM LINK:
Division 1
Division 2
Video Editorial
Author: john_smith_3
Tester: Radoslav Dimitrov
Editorialist: Srikkanth
DIFFICULTY:
Easy
PREREQUISITES:
Bitwise operations
PROBLEM:
Find a permutation of first n integers that has bitwise AND of every consecutive pair of integers greater than 0.
EXPLANATION:
If n is a power of two and n > 1, then n will be present in the permutation and will have atleast one neighbour.
None of the numbers in 1, 2, ... n-1 have bitwise AND with n greater than 0, so answer is -1 in this case.
For the first 7 numbers we can brute force and find valid solutions if any.
In all other cases we can find a pattern that satisfies the properties.
One such construction is, to group all the numbers by their highest set bit.
Consider only numbers greater than 7.
Starting from highest number in a group, list all numbers in descending order but swapping the last two.
Eg. for 3rd bit, (15, 14, ..., 8, 9)
for 4th bit, (31, 30, ..., 16, 17)
Within each group, AND is clearly greater than 0. (highest bit set in all)
Let’s append the groups in descending order of the highest set bit,
At the border between consecutive groups, bitwise AND is also greater than 0, because the last element of the first group is odd and beginning of each group is odd as well.
At the end, we can append the 7 numbers {7, 4, 5, 6, 2, 3, 1} to complete the permutation.
Eg for n = 17, we have {[16, 17], [15, 14, ..., 8, 9], [7, 4, 5, 6, 2, 3, 1]} (groupings are shown within [])
TIME COMPLEXITY:
TIME: \mathcal{O}(n)
SPACE: \mathcal{O}(1)
SOLUTIONS:
Setter's Solution
//
// posand
//
#include <bits/stdc++.h>
#include <numeric>
using namespace std;
string binary( uint32_t x )
{
string a = "";
for (uint32_t i=32; i-->0; )
{
a += (char) ('0'+ ((x>>i)&1));
a += " ";
}
return a;
}
list<uint32_t> solve( uint32_t N )
{
list<uint32_t> v;
if (N==1) {
v.insert(end(v),1);
return v;
}
uint32_t r=1;
while (r < N) r<<=1;
if (r==N) return v;
r>>=1;
v.insert(end(v), r);
for (uint32_t j=r+2; j<=N; j++)
{
v.insert(end(v),j);
}
v.insert(end(v), r+1);
for (uint32_t i=1; i<r; i++)
{
v.insert( v.end(), (i^(i>>1)) );
}
return v;
}
int main( int argc, char ** argv )
{
ios_base::sync_with_stdio(false);
uint32_t T;
cin >> T;
while (T--)
{
uint32_t N;
cin >> N;
auto v = solve(N);
if (v.size() == 0)
{
cout << -1 << endl;
}
else
{
for (auto x : v) cout << x << " ";
cout << endl;
}
}
return 0;
}
Tester's Solution
#include <bits/stdc++.h>
#define endl '\n'
#define SZ(x) ((int)x.size())
#define ALL(V) V.begin(), V.end()
#define L_B lower_bound
#define U_B upper_bound
#define pb push_back
using namespace std;
template<class T, class T1> int chkmin(T &x, const T1 &y) { return x > y ? x = y, 1 : 0; }
template<class T, class T1> int chkmax(T &x, const T1 &y) { return x < y ? x = y, 1 : 0; }
const int MAXN = (1 << 20);
int n;
void read() {
cin >> n;
}
void solve() {
if(n == 1) {
cout << 1 << endl;
return;
}
if((n & -n) == n) {
cout << -1 << endl;
} else {
cout << 2 << " " << 3 << " " << 1 << " ";
for(int l = 2; (1 << l) <= n; l++) {
cout << ((1 << l) ^ 1) << " " << (1 << l) << " ";
for(int x = (1 << l); x <= min(n, (2 << l) - 1); x++) {
if(x > 1 + (1 << l)) cout << x << " ";
}
}
cout << endl;
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while(T--) {
read();
solve();
}
return 0;
}
Editorialist's Solution
#include<bits/stdc++.h>
using namespace std;
#define LL long long int
#define FASTIO ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
const int oo = 1e9 + 5;
const LL ooll = (LL)1e18 + 5;
const int MOD = 1e9 + 7;
// const int MOD = 998244353;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define rand(l, r) uniform_int_distribution<int>(l, r)(rng)
clock_t start = clock();
const int N = 1e5 + 5;
void solve() {
int n;
cin >> n;
if (__builtin_popcount(n) == 1) {
if (n == 1) {
cout << "1\n";
} else {
cout << "-1\n";
}
return;
}
vector<int> first_seven = {0, 1, 3, 2, 6, 5, 4, 7};
if (n == 5) {
cout << "2 3 1 5 4\n";
return;
}
int pre, cur = 7;
for (int i=1;i<=min(n,7);++i) cout << first_seven[i] << " ";
for (int pw=3;(1<<pw)<=n;++pw) {
int st = (1<<pw), en = min(n+1, (st<<1));
pre = cur;
cur = st+1;
cout << cur << " ";
// if ((pre & cur) == 0) {
// cout << pre << " " << cur << " " << (pre & cur) << " failed\n";
// assert(false);
// }
pre = cur;
cur = st;
cout << cur << " ";
// if ((pre & cur) == 0) {
// cout << pre << " " << cur << " failed\n";
// assert(false);
// }
for (int i=st+2;i<en;++i) {
pre = cur;
cur = i;
// if ((pre & cur) == 0) {
// cout << pre << " " << cur << " failed\n";
// assert(false);
// }
cout << cur << " ";
}
}
cout << '\n';
}
int main() {
// FASTIO;
int T = 1;
cin >> T;
for (int t=1;t<=T;++t) {
solve();
}
// cerr << fixed << setprecision(10);
// cerr << "Time: " << (clock() - start) / (CLOCKS_PER_SEC) << " secs\n";
return 0;
}
