PROBLEM LINK:
Setter: Ritesh Gupta
Tester: Yash Chandnani
Editorialist: Ishmeet Singh Saggu
DIFFICULTY:
Medium
PREREQUISITES:
Bits and Ad-hoc
PROBLEM:
You have been given an array of N integers and have to make an array (by reordering the elements by swapping consecutive elements) such that no matter how we divide the array into 2 non-empty segments we can never be able to make bitwise OR of the elements of one segment equal to the bitwise OR of the elements of the other segment. And in case multiple arrays exist find the array which requires a minimum number of swaps to form.
QUICK EXPLANATION:
- When N=1 as in this case there will be no way to divide the array into 2 non-empty segments hence the answer will be 0.
- If an array is a good array then there will be 2 bit position i and j(i != j) such that there exists at least one number with its ith bit equals 1(or on) and jth bit equals 0(or off) in its binary representation [ let us refer to such number as type1 ], and at least one number with its jth bit equals 1(or on) and ith bit equals 0(or off) in its binary representation [ let us refer to such number as type2 ] and all the elements of the type1 are in one side and all the elements of the type2 are on the other side then no matter what partition you do in the 2 OR’s of segment either ith bit will be missing in one or jth bit will be missing in another. Now you might ask that there might be some number whose ith and jth bit both might be on [ let us refer to such number as type3 ]. In this case, when such a number exists then the array will be good if there count is equal to 1 and the element will be situated between type1 and type2 elements. If there is more count of type3 we cannot make the array good no matter what we try.
- if you have 1 element of type3 then the condition of at least 1 element of type1 and type2 is removed.
- Compute the minimum number of swaps required to form such array for all possible pairs of i and j (where i and j are not equal and satisfy the conditions mentioned above). and the minimum among those will be our answer. And if no valid pair exist then the answer is -1.
EXPLANATION:
First, let us separate the case where N=1 as in this case there will be no way to divide the array into 2 non-empty segments hence the answer will be 0. So now consider the array with N > 1.
Now one observation is that, If an array is a good array then there will be 2 bit position i and j(i != j) such that there exists at least one number with its ith bit equals 1(or on) and jth bit equals 0(or off) in its binary representation [ let us refer to such number as type1 ], and at least one number with its jth bit equals 1(or on) and ith bit equals 0(or off) in its binary representation [ let us refer to such number as type2 ] and all the elements of the type1 are in one side and all the elements of the type2 are on the other side then no matter what partition you do in the 2 OR’s of segment either ith bit will be missing in one or jth bit will be missing in another. Now you might ask that there might be some number whose ith and jth bit both might be on [ let us refer to such number as type3 ]. In this case, when such a number exists then the array will be good if there count is equal to 1 and the element will be situated between type1 and type2 elements. If there is more count of type3 we cannot make the array good no matter what we try.
Note if you have 1 element of type3 then the condition of at least 1 element of type1 and type2 is removed. As if you divide the array into two segments then type3 will only be present in one segment as its count is equal to 1 and hence the two segments will have different OR’s.
Now first let us refer to all the other numbers as type0. then to compute the minimum number of swaps such that the array will have type1 elements first then a single type3 element if it is there then all type2 elements. Note type0 elements can be anywhere and there is no restriction where they should be present as they don't affect the ith and jth bit in the OR. Now to compute the minimum swap for ith and jth bit we will follow the following algorithm.
- Create an array of size N in which number with type0 is marked with 0, type1 with 1, type2 with 2 and type3 with 3.
- Now iterate from left to right and maintain the count of type1, type2 and type3 and increment them as you encounter them,(initially initialized with 0). let us refer them as cnt1, cnt2 and cnt3.
- When we encounter a type1 element we will add cnt2 + cnt3 to our answer(in order to maintain the order).
- When we encounter a type3 element we will add cnt2 to our answer(in order to maintain the order).
- When we encounter a type0 element(note they might contribute to our answer as some of them lie in between so when we try to maintain order) they will add [ minimum(cnt3+cnt2, (totalCntType1+totalCntType2)-cnt1-cnt3) ]. Now why cnt3+cnt2, as this amount of element, will come to the right of it when there are some elements with type1 which is to the right of this element of type0. Why (totalCntType1+totalCntType2)-cnt1-cnt3) as this amount of element will come to the left of it when we try to maintain order. So for each element of type0, we will select the best option so its individual contribution to the answer in minimum.
- In this way you can compute the number of swaps required to form the answer.
Now compute it for all possible pairs of i and j (where i and j are not equal and satisfy the conditions mentioned above). and the minimum among those will be our answer. And if no valid pair exist then the answer is -1.
TIME COMPLEXITY:
- As the maximum magnitude of elements in the array is 10^6, so 20 bits in their binary representation will be enough to represent all the numbers. So the total number of i and j pairs are 400 and for each pair, we compute the minimum number of swaps in O(N). So total time complexity per test case is O(400*N).
SOLUTIONS:
Tester's Solution
#include <bits/stdc++.h>
using namespace std;
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
#define rep(i, n) for(int i = 0; i < (n); ++i)
#define repA(i, a, n) for(int i = a; i <= (n); ++i)
#define repD(i, a, n) for(int i = a; i >= (n); --i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
#define fill(a) memset(a, 0, sizeof (a))
#define fst first
#define snd second
#define mp make_pair
#define pb push_back
typedef long double ld;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
long long readInt(long long l,long long r,char endd){
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true){
char g=getchar();
if(g=='-'){
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g && g<='9'){
x*=10;
x+=g-'0';
if(cnt==0){
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);
assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd){
if(is_neg){
x= -x;
}
assert(l<=x && x<=r);
return x;
} else {
assert(false);
}
}
}
string readString(int l,int r,char endd){
string ret="";
int cnt=0;
while(true){
char g=getchar();
assert(g!=-1);
if(g==endd){
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt && cnt<=r);
return ret;
}
long long readIntSp(long long l,long long r){
return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
return readString(l,r,'\n');
}
string readStringSp(int l,int r){
return readString(l,r,' ');
}
void pre(){
}
ll sum = 0;
int a[100009],b[100009];
void solve(){
int n = readIntLn(1,1e5);
rep(i,n-1){
a[i] = readIntSp(1,1e6);
}
a[n-1] = readIntLn(1,1e6);
ll fns = 1e18;
rep(i,20){
rep(j,20){
if(i==j) continue;
vi x,y,z;
rep(k,n){
b[k]=0;
if(a[k]&(1<<i)) x.pb(k),b[k]=1;
if(a[k]&(1<<j)) y.pb(k),b[k]=3;
if((a[k]&(1<<i))&&(a[k]&(1<<j))) z.pb(k),b[k]=2;
}
if(sz(z)>1) continue;
if(sz(x)==0||sz(y)==0) continue;
ll ans = 0;
int cnt1 = 0,cnt2=0,cnt3=0;
rep(k,n){
if(b[k]==1){
ans+=cnt2+cnt3;
cnt1++;
}
if(b[k]==2){
ans+=cnt3;
cnt2++;
}
if(b[k]==3) cnt3++;
if(b[k]==0){
ans+=min(cnt2+cnt3,sz(x)-cnt1-cnt2);
}
}
fns=min(fns,ans);
}
}
if(fns==1e18) cout<<-1<<endl;
else cout<<fns<<endl;
}
int main() {
cin.sync_with_stdio(0); cin.tie(0);
cin.exceptions(cin.failbit);
pre();
int n = readIntLn(1,1e3);
rep(i,n) solve();
assert(getchar()==EOF);
assert(sum<=500000);
return 0;
}
Feel free to share your approach. In case of any doubt or anything is unclear please ask it in the comment section. Any suggestions are welcomed. 