POSAND - Editorial

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;
} 
2 Likes

Positive And: Full Explanation - Link

this is posand Editorial

3 Likes

positive AND video solution

I can’t understand what is the problem in my solution
#include<bits/stdc++.h>
using namespace std;
#define ll long long
void swap(ll *a,ll *b)
{
ll temp=*a;
*a=*b;
*b=temp;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
#ifndef ONLINE_JUDGE
freopen(“input.txt”,“r”,stdin);
freopen(“output.txt”,“w”,stdout);
#endif
ll t; cin>>t;
while(t–){
ll n; cin>>n;
ll arr[n+1]={0};
for(ll i=1;i<=n;i++)
arr[i]=i;
ll temp=(int)log2(n);
if(pow(2,temp)==n)
{
cout<<-1<<"\n";
continue;
}
else
{
ll j=1;
for(ll i=2;i<=n;i=pow(2,j))
{
if(i==2)
{
swap(&arr[i],&arr[i+1]);
swap(&arr[i-1],&arr[i+1]);
}
else if((arr[i]&arr[i-1])==0 && (arr[i]&arr[i+1])>0)
{
swap(&arr[i],&arr[i+1]);
}
j++;
}
for(ll i=1;i<=n;i++)
cout<<arr[i]<<" “;
cout<<”\n";
}
}
return 0;
}
please any body tell me?

The problem POSAND has contradictory constraints. First it says 1<=i<N. Which clearly implies N>1, and it makes sense as well. But, in the bottom it takes the constraints as 1<=N<=10^5 . I mean how can you take N=1? It doesn’t even make sense and it violates the constraints above. If you are taking N=1, the answer should be -1 not 1. Because it just doesn’t satisfy the condition of the problem. This has cost me 50 points, and 3k ranks, and an obvious rating loss. Either correct the solution or give it a bonus.

The tester’s solution is also wrong as the tester is taking the answer for n=1 as 1. Please check this.

11 Likes

Another solution.
Let k be the maximum integer that 2^k\le n.
First construct Gray code sequence from 1 to 2^k-1 (In addition, the first integer of the Gray code sequence should be 1)
Then, for 2^k+1\le i\le n, insert it before i-2^k.
At last, place 2^k at the beginning.

1 Like

Why is answer 1 for N = 1?

2 Likes

Answer for N = 1 is 1 for some unknown reasons.

1 Like

Am I understanding it wrong, or should the answer for N=1 be -1 instead of 1?

1 Like

I got it partially correct,i dont know why it failed task no #2 and #3…Please help me

#include <bits/stdc++.h>
#define fast1 ios_base::sync_with_stdio(false)
#define fast2 cin.tie(NULL)
#define ll long long
#define FOR(i,a,n) for(int i=a;i<n;i++)
#define SIZE 100001
#define pb push_back
using namespace std;
ll int Pow(ll int n);
int main()
{
fast1;
fast2;
ll int t,n;
cin>>t;
while(t–)
{
cin>>n;
if(Pow(n))
cout<<-1;
else if(n==3LL){
cout<<1<<" “<<3<<” “<<2;
}
else if(n>3){
cout<<2<<” “<<3<<” “<<1<<” “;
for(ll int i=4LL;i<=n;i++)
{
if(Pow(i))
{
cout<<i+1LL<<” “<<i<<” “;
i++;
}
else
cout<<i<<” “;
}
}
cout<<”\n";
}
}
ll int Pow(ll int n)
{
if ((n & (n-1LL))==0)
return 1LL;
return 0LL;

}

One way to do it was to print all numbers in sequence and when a number comes with power of 2 then print its next number first(i+1) and then print i.
Given pseudo code for n>=4

print(2,3,1)
i=4
while(i<=n):
if (math.log(i,2)==0):
print(i+1,i)
i=+2
else:
print(i)
i+=1

1 Like

if i am not wrong. condition was that there should be no pair (a_i, a_j) such that (a_i \& a_j == 0) .
if n = 1 there are no pairs hence condition satisfied.

1 Like

The first statement specifies the required condition, not the constraints.

if pi&pi+1 is greater than 0 for every 1≤i<N

This is a formal way of stating that every pair starting from the first index should have greater than 0 bitwise AND with its neighbors. This is not related to the constraints at all.

In the case of just 1, there are no pairs, so the condition is already satisfied.

There is nothing wrong with having this confusion.

But Instead of trying to find the reason, you are just blaming the question Writers and Testers, which is not a good way of dealing with such problems. Unfortunately, The latter has become more common on platforms like Codechef in recent times.

In Depth Analysis and elaborate thought process to reach solution ideas and correct code implementation

https://tinyurl.com/y5msjfc3

In depth analysis and reaching key observations, correct code implementation

https://www.codechef.com/viewsolution/38729676
what is wrong with this solution , it is partially accepted

Your code would print -1 in the case when n = 1, while the correct answer is 1. It is a valid permutation as there are no pairs for the condition to fail.

I have uploaded a detailed solution on my YouTube channel. You can watch it.