ASFA - Editorial

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)