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:
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;
}
