CDEC2207-Editorial

asmit0701 · April 23, 2022, 1:35pm

PROBLEM LINK:

DIFFICULTY:

MEDIUM.

PREREQUISITES:

Graph Theory

PROBLEM:

The problem is a perfect example of restricted sorting. We have to sort the given array with the restriction that only the elements with Bitwise AND \neq 0. If the array can be sorted, we output “YES” else we output “NO”.

EXPLANATION:

The main idea behind the problem is trying to figure out a way to find the numbers that can swap places among themselves. This can easily be achieved by placing the indices of such numbers in the same connected component of a graph. To do this, we iterate repeatedly through the array and place an edge between any two indices that have at least one common set bit. We then find connected components using depth first search. We then check if the required swaps are possible or not.

SOLUTIONS:

Setter's Solution

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
vector<int> g[300001];
int col[300001];
int vis[300001];


void dfs(int node,int c)
{
    vis[node]=1;
    col[node]=c;
    for(int i:g[node])
    {
        if(vis[i]==0)
        {
            dfs(i,c);
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        for(int i=0;i<n;i++)
        {
            col[i]=0;
            vis[i]=0;
            g[i].clear();
        }
        vector<pair<int,int>> v;
        int a[n];
        for(int i=0;i<n;i++)
        {
            cin>>a[i];
            v.push_back(make_pair(a[i],i));
        }
        int flag=0;
        int temp=-1;
        while(flag==0)
        {
           flag=1;
           temp=-1;
           for(int i=0;i<n;i++)
           {
               if(a[i]!=0)
               {
                  flag=0;
                  if(a[i]%2==1)
                  {
                      if(temp==-1)
                      temp=i;
            
                      else
                      {
                          g[temp].push_back(i);
                          g[i].push_back(temp);
                      }
                  }
                  a[i]/=2;
              }
          }
       }
    int ptr=0;
    for(int i=0;i<n;i++)
    {
        if(vis[i]==0)
        {
            dfs(i,ptr);
            ptr++;
        }
    }
    sort(v.begin(),v.end());
    flag=1;
    for(int i=0;i<n;i++)
    {
        if(v[i].second==i||col[v[i].second]==col[i])
        continue;
        
        flag=0;
        break;
    }
    if(flag==1)
    cout<<"Yes\n";
    else
    cout<<"No\n";
}
return 0;
}

Tester's Solution

#include <bits/stdc++.h>
using namespace std;

int sumOfN=0;

string solve(){
    int n;
    cin>>n;
    assert(n>=1&&n<=3*1e5);
    sumOfN+=n;
    vector<pair<int,int>>p;
    for(int i=0;i<n;i++){
        int input;
        cin>>input;
        assert(input<=INT_MAX&&input>=0);
        p.push_back({input,-1});
    }
    int component=0;
    for(int i=0;i<n;i++){
        if(p[i].second!=-1)
            continue;
        bool flag=true;
        int value=p[i].first;
        p[i].second=component;
        while(flag){
            flag=false;
            for(int j=i+1;j<n;j++){
                if(p[j].second==component)
                    continue;
                if(((p[j].first)&value)==0)
                    continue;
                flag=true;
                p[j].second=component;
                value|=p[j].first;
            }
        }
        component++;
    }
    vector<pair<int,int>>v=p;
    sort(v.begin(),v.end());
    for(int i=0;i<n;i++){
        if(v[i].second!=p[i].second)
            return "No";
    }
    return "Yes";
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    // your code goes here
    int test;
    cin>>test;
    assert(test>=1&&test<=1e4);
    while(test--)
        cout<<solve()<<endl;
    assert(sumOfN<=3*1e5);
    return 0;
}