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)