PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: danishiitp_24
Tester: yash_daga
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
None
PROBLEM:
Given a boolean array A of length N, in one move you can select two distinct indices i and j, and set both A_i and A_j to A_i \oplus A_j.
Find the minimum number of moves to obtain an array with an equal number of zeros and ones.
EXPLANATION:
If N is odd, the answer is clearly -1, so we only care about the even case.
Suppose the array initially has x zeros and y ones.
Note that since N is even, x and y will definitely have the same parity.
Our objective is to end up with x = y.
Let’s analyze what exactly our operation can do:
- Operating on two zeros does nothing
- Operating on two ones changes them both to zeros. This increases x by 2 and decreases y by 2.
- Operating on a zero and a one changes the zero into a one, increasing y by 1 and decreasing x by 1.
With this in hand, we can do a bit of casework.
y ≤ x
If x = y the answer is clearly zero.
Otherwise, we need to increase y and decrease x.
Notice that our operations only allow us to increase y by 1 and decrease x by 1 in one step.
In particular, this shortens the distance between x and y by two.
So, if d = x - y, we need exactly \frac{d}{2} steps to make them equal.
However, there is one edge case here: if y = 0, then the answer is -1, since if the array is filled with zeros we can’t actually turn anything into a 1.
y > x
Let d = y - x. We want to end up with d = 0.
Our operations allow us to either decrease d by 4 or increase it by 2.
So,
- If d is a multiple of 4, we need \frac{d}{4} moves.
- If d is not a multiple of 4, we need \frac{d}{4} + 2 moves, since we need to spend one move increasing d by 2 before we reduce it to zero.
Once again, there’s a small edge case here.
If d is not a multiple of 4 and y = 2, the answer is -1.
This is because the array will have two ones and no zeros, i.e, A = [1, 1]. There’s no way to turn exactly one of these ones into a zero.
TIME COMPLEXITY
\mathcal{O}(N) per testcase.
CODE:
Setter's code (C++)
#include <bits/stdc++.h>
#include<string>
#define int long long
using namespace std;
signed main()
{
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
vector< int > v(n);
for(auto &x:v)
cin>>x;
int odd=0,even=0;
for(auto i:v)
{
if(i%2)
++odd;
else
++even;
}
if(n%2)
cout<<-1;
else {
if(even==odd)
cout<<0;
else if(even>odd){
if(odd)
cout<<(even-odd)/2;
else
cout<<-1;
}
else{
int ans=odd-even;
if(ans%4==0)
cout<<ans/4;
else if(odd==2)
cout<<-1;
else
cout<<(ans-2)/4+2;
}
}
cout<<"\n";
}
return 0;
}
Tester's code (C++)
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin>>t;
assert(t<=700 && t>0);
int sumn=0;
while(t--)
{
int n;
cin>>n;
assert(n>=1 && n<=100000);
sumn+=n;
assert(sumn<=200000);
int o=0, z=0;
for(int i=0;i<n;i++)
{
int a;
cin>>a;
assert(a==0 || a==1);
o+=(a==1);
z+=(a==0);
}
if((n&1) || o==0 || (n==2 && o==2))
cout<<-1<<'\n';
else if(z>o)
cout<<((z-o)/2)<<'\n';
else
cout<<((o-z)/4) + (o-z)%4<<'\n';
}
}
Editorialist's code (Python)
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
if n%2 == 1:
print(-1)
continue
zeros, ones = a.count(0), a.count(1)
if ones >= zeros:
dif = ones - zeros
if dif%4 == 0: print(dif//4)
elif ones == 2: print(-1)
else: print(dif//4 + 2)
else:
dif = zeros - ones
print(dif//2 if ones > 0 else -1)