Bitwise swaps BITSWAPS Solution Codechef

Codechef Bitwise swaps BITSWAPS Solution

Given an array AA consisting of NN integers A1,A2,…,ANA1,A2,…,AN, determine if you can sort this array by applying the following operation several times (possibly, zero):

  • Pick a pair of indices (i,j)(i,j) with i≠ji≠j and Ai&Aj≠0Ai&Aj≠0, and swap the values of AiAi and AjAj. Here, && denotes the bitwise AND operation.

For example, if A=[6,4,2]A=[6,4,2], the two possible operations are (1,2)(1,2) and (1,3)(1,3). (2,3)(2,3) cannot be performed because A2&A3=4&2=0A2&A3=4&2=0.

Input Format

  • The first line of input contains a single integer TT, denoting the number of test cases. The description of TT test cases follows.
  • The first line of each test case contains a single integer NN.
  • The second line contains NN space-separated integers A1,A2,…,ANA1,A2,…,AN

Output Format

For each test case, output the answer on a new line — YES if the given array can be sorted by repeatedly applying the given operation, and NO otherwise.

You may print each character of the answer string in either uppercase or lowercase (for example, the strings "yEs""yes""Yes" and "YES" will all be treated as identical).

Constraints

  • 1≤T≤1041≤T≤104
  • 1≤N≤3⋅1051≤N≤3⋅105
  • 0≤Ai<2310≤Ai<231 for each 1≤i≤N1≤i≤N
  • The sum of NN over all test cases does not exceed 3⋅1053⋅105

Subtasks

Subtask #1 (100 points): Original constraints

Sample Input 1 

4
3
6 4 2
6
9 34 4 24 1 6
6
9 34 24 4 1 6
2
1 0

Sample Output 1 

Yes
Yes
No
No

Explanation

Test case 11: AA can be sorted by applying the single operation (1,3)(1,3).

Test case 22: AA can be sorted by applying the following operations in order: (1,5),(2,6),(2,3),(4,5)(1,5),(2,6),(2,3),(4,5).

Test cases 33 and 44: It can be shown that no sequence of operations will sort AA.

SOLUTION

Program: Bitwise swaps BITSWAPS Solution in C++

#include <bits/stdc++.h>
using namespace std;
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int t;
	cin>>t;
	while(t--){
	    int n;
	    cin>>n;
	    map<int,int> mp;
	    vector<int> arr(n),temp(n);
	    for(int i=0;i<n;i++){
	        cin>>arr[i];
	        mp[arr[i]]=i;
	        temp[i] = arr[i];
	    }
	    
	    sort(temp.begin(),temp.end());
	    vector<int> visited(n,0),visBit(32,0);
	    int k = 1;
	    for(int i=0;i<32;i++){
	        unsigned int nN = 1<<i;
	        for(int j=i;j<32;j++){
	            unsigned int t = 1<<j;
	            if(visBit[j]||(nN&t)==0)
	            continue;
	            visBit[j] = 1;
	            for(int l=0;l<n;l++){
	                bool cnd = ((visited[l]==0)&&(arr[l]&nN));
	                if(cnd){
	                    nN = nN|arr[l];
	                    visited[l]=k;
	                }
	            }
	            
	        }
	        k++;
	    }
	    k=1;
	    for(int i=0;i<n;i++)
	        auto itr = mp.find(temp[i]);
	        if(visited[i]!=visited[itr->second]){
	            k=0;
	            break;
	        }
	    }
	    if(k)
	    cout<<"Yes\n";
	    else
	    cout<<"No\n";
	}
	return 0;
}

February Long 2022 – II (Rated for Div 3)

Leave a Comment

fifteen + 4 =