P4169 - Editorial

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: pols_agyi_pols
Tester: kingmessi
Editorialist: iceknight1093

DIFFICULTY:

Simple

PREREQUISITES:

None

PROBLEM:

You’re given a permutation P.
You can swap P_i and P_j if they have the same number of ones in their binary representations. Is it possible to sort P by performing several such swaps?

EXPLANATION:

Let’s look at the element x, say with c_x ones in its binary representation.
This element can only be swapped with some other element with c_x ones in its representation.
For P to be sorted, element x should end up at position x.

This is only possible if P_x also has c_x ones in its binary representation, i.e, c_{P_x} = c_x.

Why?

Note that for any i, the number of ones of the element at index i is a constant - swapping won’t change it.
So, if c_{P_x} \neq c_x, it’s impossible for x to ever end up at position x.
If c_{P_x} = c_x, x can be placed at position x with a single swap.

This leads to a very simple solution: for each i from 1 to N, check if i and P_i have the same number of ones in their binary representations.
If this condition is true for all i then sorting P is possible; otherwise it’s not possible.

Counting the number of ones in the binary representation of an integer can be done in \mathcal{O}(\log N) time by just iterating over bits; or in constant time using inbuilt functions in certain languages (like __builtin_popcount or std::popcount in C++ - note that the latter only works on unsigned integer types).

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Author's code (C++)
#include <bits/stdc++.h>
using namespace std;
#define ll long long

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
  ll cases=1;  
  cin>>cases;
  while(cases--){
    ll n;
    cin>>n;
    ll x;
    ll flag=0;
    ll cnt;
    for(int i=1;i<=n;i++){
      cin>>x;
      cnt=__builtin_popcountll(x);
      cnt-=__builtin_popcountll((ll)i);
      if(cnt!=0){
        flag++;
      }
    }
    if(flag){
      cout<<"No\n";
    }else{
      cout<<"Yes\n";
    }
  }
	return 0;
}
Editorialist's code (PyPy3)
for _ in range(int(input())):
    n = int(input())
    p = list(map(int, input().split()))
    ans = 'Yes'
    for i in range(n):
        if bin(i+1).count('1') != bin(p[i]).count('1'):
            ans = 'No'
    print(ans)
2 Likes

This solution is quite good.

But i think most people(including me) would have done by sorting the elements in the same component of same count of set bits and then reassigning the sorted components and checking if its a valid permutation.

1 Like