BITSWAPS - Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3

Setter: Nabil Boudra
Tester: Manan Grover, Tejas Pandey
Editorialist: Kanhaiya Mohan

DIFFICULTY:

Easy

PREREQUISITES:

Disjoint Set Union

PROBLEM:

Given an array A consisting of N integers A_1, A_2, …, A_N, determine if you can sort this array by applying the following operation several times (possibly, zero):

  • Pick a pair of indices (i, j) with i \neq j and A_i \& A_j \neq 0, and swap the values of A_i and A_j. Here, \& denotes the bitwise AND operation.

QUICK EXPLANATION:

  • An element can take 31 bits at maximum. Use DSU to connect bit positions i and j such that there exists an element which has both i^{th} and j^{th} bit equal to 1.
  • Let B denote the sorted version of array A. A sequence of operations can sort array A if it is possible to swap (A_i, B_i) for all (1 \leq i \leq N).
  • Look for bit positions (j, k) where A_i has the j^{th} bit equal to 1 and B_i has the k^{th} bit equal to 1 such that j and k belong to the same disjoint set.

EXPLANATION:

Wrong Approach

Let B denote the sorted version of array A. A lot of implementations were based on the idea:

  • If for a particular position A_i \neq B_i, check if (A_i \& B_i \neq 0) and swap them. If A_i \& B_i = 0, we cannot sort the array.

This approach is not correct as a third element can be used to swap (A_i, B_i). See Hint 1 for details.

Hint 1

For a given element X, let [S_1, S_2, .., S_M] be the positions of set bits in X.

Two elements Y and Z (Y \& Z = 0) can be swapped if there exists an element X with positions of set bits S such that S_i^{th} bit of Y and S_j^{th} bit of Z are 1. In other words, X shares a common set bit with both Y and Z.

How?

Consider three elements X, Y and Z such that X \& Y \neq 0, X \& Z \neq 0 and Y \& Z = 0. This means that we can directly swap (X, Y), (X,Z) but not (Y,Z).

However we can swap (Y,Z) indirectly as:

[X,Y,Z] \xrightarrow[\text{}]{swap(X,Y)} [Y,X,Z] \xrightarrow[\text{}]{swap(X,Z)}[Y,Z,X] \xrightarrow[\text{}]{swap(X,Y)} [X,Z,Y].

Hint 2

The elements of array A can take 31 bits at maximum.

Two bits i and j (1 \leq i < j \leq 31) can be grouped together if there exists an element X in A such that the i^{th} and j^{th} bit of X are equal to 1.
This X can be further used to swap (Y,Z) where Y \& Z = 0 but Y and Z have i^{th} and j^{th} bit equal to 1 respectively.

The grouping of bits can be implemented using Disjoint Set Union. We traverse each bit of an element in O(log_2(A_i)) time. Considering that we perform queries on bit positions and there can be a maximum of only 31 bits, we can say that DSU queries take constant time in this case.

Solution

To make disjoint groups of bit positions, we iterate through each element. For a given element X, let [S_1, S_2, .., S_M] be the positions of set bits in X. Then all bit positions [S_1, S_2, .., S_M] are to be grouped together.

Let B denote the sorted version of array A. A sequence of operations can sort array A if it is possible to swap (A_i, B_i) for all (1 \leq i \leq N).

How to do this?
We need to look for bit positions (j, k) where A_i has the j^{th} bit equal to 1 and B_i has the k^{th} bit equal to 1 such that j and k belong to the same group. This would make sure that we can swap (A_i, B_i) directly/indirectly.

TIME COMPLEXITY:

Let C denote the number of bits in the maximum value of A_i, (C = log_2(A_i)). Also, we need to sort the array to get B in O(Nlog(N)). Based on the implementation, the overall time complexity is O(N log(N) + N\cdot C^2) or O(Nlog(N) + N \cdot C) per test case.

SOLUTION:

Setter's Solution
#include <bits/stdc++.h>
using namespace std; 
vector<int> vis(31),a; 
void dfs(int bit,int clr){
	vis[bit]=clr; 
	for(int x : a)
		if((1<<bit)&x)
            for(int i=0;i<31;i++)
                if(((1<<i)&x)&&vis[i]==0)
					dfs(i,clr);
    return; 
}
int main(){
    ios_base::sync_with_stdio(0); 
    cin.tie(nullptr); 
    int t ;
    cin>>t; 
    while(t--){
        int n; 
        cin>>n; 
		a.resize(n); 
        for(int&x:a)cin>>x; 
		for(int&x:vis)x=0; 
        int cnt=0; 
        for(int bit=0;bit<31;bit++)
            if(vis[bit]==0)
                dfs(bit,++cnt); 
        vector<int> color(n,-1); 
        set<int> c; 
        for(int i=0;i<n;i++){
            for(int j=0;j<31;j++)
                if((1<<j)&a[i])
                    color[i]=vis[j]; 
            if(color[i]!=-1)
                c.insert(color[i]) ; 
        }
        vector<int> b(n); 
        for(int x : c){
            vector<int> index , values; 
            for(int i=0;i<n;i++)
                if(color[i]==x){
                    index.push_back(i); 
                    values.push_back(a[i]); 
                }
            sort(values.begin(),values.end()); 
            for(int i=0;i<index.size();i++)
                b[index[i]]=values[i]; 
        }
        for(int i=0;i<n;i++)
            if(a[i]==0)
                b[i]=0; 
        sort(a.begin(),a.end()); 
        if(a==b) cout << "Yes"; 
        else cout << "No"; 
        if(t) cout << endl; 
    }  
    return 0 ; 
}
Tester's Solution
#include <bits/stdc++.h>
using namespace std;

int dsu[31];

int fnd(int a) {
    return (dsu[a] == a?a:dsu[a] = fnd(dsu[a]));
}

void unite(int a, int b) {
    a = fnd(a);
    b = fnd(b);
    if(a == b) return;
    dsu[a] = b;
}

int main() {
	int t;
	cin >> t;
	while(t--) {
		int n; cin >> n;
	    int a[n], b[n];
	    for(int i = 1; i < 31; i++) dsu[i] = i;
	    for(int i = 0; i < n; i++) cin >> a[i];
	    for(int i = 0; i < n; i++) b[i] = a[i];
	    sort(b, b + n);
	    for(int i = 0; i < n; i++) {
	        for(int j = 0; j < 31; j++)
	            for(int k = j + 1; k < 31; k++)
	                if((a[i]&(1LL<<j)) && (a[i]&(1LL<<k)))
	                    unite(j, k);
	    }
	    int good = 1;
	    for(int i = 0; i < n; i++) {
	        if(!a[i] && !b[i]) continue;
	        int bad = 1;
	        for(int j = 0; j < 31; j++)
	            for(int k = 0; k < 31; k++)
	                if((a[i]&(1LL<<j)) && (b[i]&(1LL<<k)) && fnd(j) == fnd(k))
	                    bad = 0;
	        if(bad) good = 0;
	
	    }
	    cout << (good?"YeS":"NO") << "\n";
	}
	return 0;
}
Editorialist's Solution
#include <bits/stdc++.h>
using namespace std;

#define sync {ios_base ::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);}
#define rep(n) for(int i = 0;i<n;i++)
#define rep1(a,b) for(int i = a;i<b;i++)
#define int long long int
#define mod 1000000007

int n;

class DisjointSet
{
public:
   vector<int> parent;
 
   DisjointSet(int n) : parent(n)
   {
      for (int i = 0; i < n; i++)
         parent[i] = i;
   }
 
   void join(int a, int b) { parent[find(b)] = find(a); }
 
   int find(int a) { return a == parent[a] ? a : parent[a] = find(parent[a]); }
 
   bool check(int a, int b) { return find(a) == find(b); }
};

void solve()
{
    cin>>n;
    int a[n], b[n];

    DisjointSet dsu(31);
    for(int i = 0; i < n; i++){
        cin>>a[i];
        b[i] = a[i];
        int last = -1;
        for(int j = 0; j<31; j++){
            if(a[i]&(1<<j)){
                if(last==-1) last = j;
                else dsu.join(last, j);
            }
        }
    }
    sort(b, b+n);
    bool poss = true;
    for(int i = 0; i<n; i++){
        bool found = false;
        if(a[i]==0 && b[i]==0){
            found = true;
        }
        else{
            for(int j = 0; j<31; j++){
                for(int k = 0; k<31; k++){
                    if(a[i]&(1<<j) && b[i]&(1<<k) && dsu.check(j, k)){
                        found = true;
                    }
                }
            }
        }
        poss &= found;
    }
    poss?cout<<"Yes":cout<<"No";
}

int32_t main()
{

    #ifndef ONLINE_JUDGE
        freopen("input.txt","r",stdin);
        freopen("output.txt","w",stdout);
    #endif
    
    sync;
    int t = 1;
    cin>>t;
    while(t--){
        solve();
        cout<<"\n";
    }
    return 0;
}
5 Likes

Can somebody tell why is my code showing TLE?
https://www.codechef.com/viewsolution/58393743

in this bitswaps question
i pass last three test case but not getting passed in first two test case can anyone help
my code:-
#include<bits/stdc++.h>
#define IO ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define PI 3.141592653589793238462
#define ll long long
#define ld long double
#define INF 1e18
#define MOD 998244353
#define eps 1e-9
//if(abs(a-b)<eps) → a==b
using namespace std;

void solve(){
ll n;
cin>>n;
vectorA(n);
unordered_map<ll,vector> mp;
for(int i=0;i<n;i++){
cin>>A[i];
}

vector<ll>B =A;
sort(all(B));

for(int i=0;i<n;i++){
    if(B[i]!=A[i]){
        mp[A[i]].pb(i);
    }
}

//finding a intermediate no. so that we can swap 
//the no. which a&b =0
// we have to find a no. that a&c !=0 , c&b !=0 

bool ans = true;
for(int i=0;i<n;i++){
    if(B[i]!=A[i]){
        ll found =0;
        for(auto it:A){
            if(((A[i]&it) !=0) && ((B[i]&it) !=0)){

                ll ind = *(mp[B[i]].begin());
                mp[B[i]].erase(mp[B[i]].begin());
                auto it = find(all(mp[A[i]]) ,i);
                mp[A[i]].erase(it);

                //swap
                A[ind] = A[i];
                A[i] = B[i];

                if(B[ind]!=A[ind]){
                    mp[A[ind]].pb(ind);
                }
                found =1;
                break;
            }
        }
        if(!found){
            ans =false;
            break;
        }
    }
}

cout<<(ans?"Yes":"No")<<endl;

}

int main(){
IO;
ll t =1;
cin>>t;
while(t–){
solve();
}
return 0;
}

1 Like

Sir, can’t we make a graph of indices of a array in which a edge occurs if a[i]&a[j]!=0.
By using disjoint set union.
I tried to sove the same problem using two nested for loop but getting TLE
https://www.codechef.com/viewsolution/58328901
O(N^2) should work since n=10^5 and time is 2 sec

A clean approach

#include<bits/stdc++.h> 
using namespace std;
class DisjointSet{
    unordered_map<int,int> parent,rank;

    public : 
    DisjointSet(vector<int> elem){
        for(auto el : elem){
            parent[el] = el;
            rank[el] = 0;
        }
    }
    int findparent(int u){
        if(parent[u] == u) return u;
        return parent[u] = findparent(parent[u]);
    }
    bool are_same(int a, int b){
        return findparent(a) == findparent(b);
    }
    void Union(int u, int v){
        int parent_u = findparent(u);
        int parent_v = findparent(v);
        if(rank[parent_u] > rank[parent_v]){
            parent[parent_v] = parent_u;
            rank[parent_u] ++ ;
        }else{
            parent[parent_u] = parent_v;
            rank[parent_v] ++ ;
        }
        
    }
 
};

void solve()
{
    int t, n;
    cin >> t;
    while(t--){
        cin >> n;
        vector<int> x(n);
        for(auto &elem : x) cin >> elem;
        DisjointSet dj(x);
        vector<int> data[32],pos[32];
        for(int i = 1; i <= 31; i++ ){
            for(int j = 0; j < n ; j++ ){
                if(x[j] & (1 << (i-1))) data[i].push_back(x[j]);
            }
        }
        for(int i = 1; i <= 31; i++ ){    
        for(int j = 1; j < data[i].size(); j++ ){
            dj.Union(data[i][0], data[i][j]);
        }
    
        }

        vector<int> y = x;
        sort(y.begin(),y.end());
        bool ans = true;
        for(int i = 0; i < n ; i++){
            ans = ans and dj.are_same(x[i], y[i]);
        }
        ans?cout<<"Yes\n":cout<<"No\n";
    }
}
int main()
{
ios_base::sync_with_stdio(false);
cout.tie(NULL);
cin.tie(NULL);
solve();
return 0;
}
11 Likes

can you please tell what you done i m unable to understand please hel;p

That is exactly what I did make a graph but instead of O(nn) I used bits to make a graph in O(32n)!
here is my sol: Solution: 58243465 | CodeChef

Thank you for helping. Correct me if i am wrong you used set bits of element in order to bunch them together and then create edges… Right?

  1. If any of the two numbers have any bit common then they can be swapped.
    Also consider the case where we have three numbers a, b, c. Say a and b have a set bit common and similarly b and c. Then, a and c can be also swapped indirectly through b

So, these numbers that have their set bits common can be put in same groups using DSU.

  1. Now make a copy of original array and sort it.

  2. Now check for every index that elements in new array and original array lie in same grp Or not. If so, then answer is yes else no

3 Likes

No O(n^2) will not work in 2 sec. It wont work in 4 sec either.

Oh sorry my bad 2sec is 2*10^8 operation

yes, as if the ith bit is set in two numbers their & will always be greater than 0!

ah! DSU saves a lot of work !
will learn it then:)

1 Like

can someone tell me why every solution uses left shift operations << on j and k ?
is it somewhere mentioned in editorial, and I am unable to get it?

The approach I followed is to generate the graph and assign Forest Number.
If at each position, the forest number of both sorted list and original list is same, it means the list could be sorted. However for the first case my solution generates the error, I would like to know on which edge case this code fails,
https://www.codechef.com/viewsolution/58393264

It’s difficult to figure out if this is Confidence or Innocence. I solved it in 1024\times N but still doubted if it would pass.

1 Like

X & (1 << i) will be positive if i^{th} bit (from right) is set in X. The same will return 0 otherwise.

the core logic is that
we can get form x y z (x shares with y and y shares with z) to any combination we want
I don’t know why I was thinking that it is not possible to do so .

Nice problem :slight_smile:

Editorialist’s Solution will give “NO” for this test case
8
0 0 9 34 4 24 1 6
but it should be “YES”.He should also take care of zeroes.