BITBLEND - Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3

Setter: Akshit Monga
Tester: Tejas Pandey
Editorialist: Kanhaiya Mohan

DIFFICULTY:

Easy

PREREQUISITES:

Bitwise Operation

PROBLEM:

Chef calls a sequence of integers A_1, A_2, …, A_N \texttt{tasty} if it satisfies the condition

  • parity(A_i \& A_{i+1}) \neq parity(A_i | A_{i+1}) for all 1 \leq i <N.

Given a sequence A of length N. You may perform following operation on the sequence any number of times (possible 0):

  • Choose 2 indices i and j (1 \leq i,j \leq N ; i \neq j) and change A_i to A_i ⊕ A_j.

Chef is asking you to make the sequence tasty using the minimum number of operations, or report that it is impossible.

QUICK EXPLANATION:

  • A sequence is tasty if the elements have alternating parity.
  • In one operation, we can change the parity of any element i by choosing a j such that A_j is odd.
  • The answer is -1 if the sequence has no odd elements.
  • To find minimum operations, we can assume the sequence to start from an odd/even element and check the number of mismatches in each case.
  • To find a sequence of operations, choose one odd element and correct all other elements using this element. Keep in mind, you might also need to correct the chosen odd element.

EXPLANATION:

What is a tasty sequence?

We are given that a sequence is tasty, if the parity of bitwise and of consecutive elements is not equal to the parity of their bitwise or.

Possible Cases

Let us consider all possible parities of consecutive elements.

The condition holds true when consecutive elements have unequal parity. In other words, a sequence is tasty, if the elements of the sequence have alternating parity.

The sequence would be either of these two forms:

  • odd, even , odd, even, ...
  • even, odd, even, odd, ...
Explaining an Operation

In one operation, we choose two indices i, j (i \neq j) and change A_i to A_i ⊕ A_j.

Possible Cases

Let us consider all possible parities of A_i and A_j.

In one operation, we can change the parity of any element i by choosing a j such that A_j is odd.

When is the answer -1?

We know that, to change the parity of an element, we need another odd element. This means that if a sequence has only even elements, we can never convert it to a tasty sequence and thus the answer is -1 in that case.

Minimum number of Operations

If there is at least one odd element in the sequence, we can always convert it to a tasty sequence.

It takes exactly one move to change the parity of an element. We can assume the sequence to start from an odd/even element and check the number of mismatches in each case. The case with lesser mismatches is optimal and would require minimum number of operations.

Possible sequence of Operations

By now, we know whether we should start the sequence with an odd element, or an even element.

One possible sequence of operations would be:

  • Correct the first two elements using the last odd element of the sequence.
  • Correct the rest of the sequence using the first odd element of the updated sequence.

Note that this would not fail even if the last odd element of the initial sequence is amongst the first two positions.

You can have any other sequence as well. Just keep in mind that the element you choose for changing the rest of the sequence might also be a mismatch.
You can see the editorialist’s solution for implementation details.

Alternate Implementation

Claim: We can always have an index with odd element such that it is not a mismatch.
Proof: Let us assume that there is no odd element such that it is not a mismatch OR all odd elements are a mismatch.
The two possible tasty sequences are:

  • Starting from odd element: Since the odd elements are mismatch, all odd positions must have even numbers. Thus, it is optimal to choose the sequence starting with even element since atleast half elements in the sequence are even and matched. This means that the odd elements, which are placed at even positions are not a mismatch.
  • Starting from even element: Since the odd elements are mismatch, all even positions must have even numbers. Thus, it is optimal to choose the sequence starting with odd element since atleast half elements in the sequence are even and matched. This means that the odd elements, which are placed at odd positions are not a mismatch.

Hence, proved by contradiction that we can always have an index with odd element such that it is not a mismatch.

We can use this element to change all other elements of the sequence. You can see setter’s solution for implementation details.

TIME COMPLEXITY:

The time complexity is O(N) per test case.

SOLUTION:

Setter's Solution (Python)
'''Author- Akshit Monga'''
from sys import stdin, stdout
input = stdin.readline
t = int(input())
for _ in range(t):
    n=int(input())
    a=[int(x) for x in input().split()]
    if [ele%2 for ele in a].count(1)==0:
        print(-1)
        continue
    x=delta=0
    for i in range(n):
        if a[i]%2!=i%2:
            x+=1
    if x>n-x:
        delta+=1
    ind=-1
    for i in range(n):
        if a[i]%2 and (i+delta)%2:
            ind=i
            break
    assert ind!=-1
    ops=[]
    for i in range(n):
        if a[i]%2!=(i+delta)%2:
            ops.append((i+1,ind+1))
    print(len(ops))
    assert len(ops)==min(x,n-x)
    for i in ops:
        a[i[0]-1]^=a[i[1]-1]
        print(*i)
    for i in range(n-1):
        assert a[i]%2!=a[i+1]%2
Setter's Solution (C++)
//Author- Akshit Monga
#include <bits/stdc++.h>
using namespace std;

int main()
{
	int T; cin>>T;
	while(T--){
		int n; cin>>n;
	  	int arr[n];
	  	bool all_even=1;
	  	for(int i=0;i<n;i++){
	  		cin>>arr[i];
	  		if(arr[i]%2) all_even=0;
	  	}
	  	if(all_even){
	  	    cout<<-1<<'\n';
	  	    continue;
	  	}
	  	int x=0,delta=0;
	  	for(int i=0;i<n;i++){
	  	    if((arr[i]%2)!=(i%2)) x++;
	  	}
	  	if(x>n-x)delta=1;
	  	int ind=-1;
	  	for(int i=0;i<n;i++){
	  	    if((arr[i]%2) and ((i+delta)%2)){
	  	        ind=i;
	  	        break;
	  	    }
	  	}
	  	assert(ind!=-1);
	  	vector<array<int,2>> ops;
	  	for(int i=0;i<n;i++){
	  	    if((arr[i]%2)!=((i+delta)%2)){
	  	        ops.push_back({i+1,ind+1});
	  	    }
	  	}
	  	cout<<(int) ops.size()<<'\n';
	  	assert((int) ops.size()==min(x,n-x));
        for(auto inds:ops){
            cout<<inds[0]<<" "<<inds[1]<<'\n';
        }
	}    
}
Tester's Solution
#include <bits/stdc++.h>
using namespace std;

int main() {
	int t;
	cin >> t;
	while(t--) {
		int n;
		cin >> n;
		int a[n];
		int cnt[2][2];
	    memset(cnt, 0, sizeof(cnt));
	    for(int i = 0; i < n; i++) cin >> a[i], cnt[i&1][a[i]&1]++;
	    if(cnt[0][1] + cnt[1][1] == 0) cout << "-1\n";
	    else {
	        if(cnt[0][1] == 0 || cnt[0][1] + cnt[1][0] < cnt[1][1] + cnt[0][0]) {
	                cout << cnt[0][1] + cnt[1][0] << "\n";
	                int first = 0;
	                for(int i = 1; i < n; i+=2)
	                    if(a[i]&1)
	                        first = i;
	                for(int i = 1; i < n; i+=2)
	                    if(!(a[i]&1))
	                        cout << i + 1 << " " << first + 1 << "\n";
	                for(int i = 0; i < n; i+=2)
	                    if(a[i]&1)
	                        cout << i + 1 << " " << first + 1 << "\n";
	        } else {
	                cout << cnt[1][1] + cnt[0][0] << "\n";
	                int first = 0;
	                for(int i = 0; i < n; i+=2)
	                    if(a[i]&1)
	                        first = i;
	                for(int i = 0; i < n; i+=2)
	                    if(!(a[i]&1))
	                        cout << i + 1 << " " << first + 1 << "\n";
	                for(int i = 1; i < n; i+=2)
	                    if(a[i]&1)
	                        cout << i + 1 << " " << first + 1 << "\n";
	        }
	    }
	}
	return 0;
}
Editorialist's Solution
#include <iostream>
#include <vector>
using namespace std;

void generateMoves(vector<int>& a){
    int n = a.size();
    int startOddMoves = 0;
    int startEvenMoves = 0;
    int lastOddPos = -1;
    for(int i = 1; i<=n; i++){
        if(i%2){
            if(a[i-1]%2) startEvenMoves++;
            else startOddMoves++;
        }
        else{
            if(a[i-1]%2) startOddMoves++;
            else startEvenMoves++;
        }
        if(a[i-1]%2) lastOddPos = i;
    }
    
    if(startOddMoves<startEvenMoves){
        cout<<startOddMoves<<endl;
        for(int i = 1; i<=n; i++){
            if(i%2){
                if(a[i-1]%2==0)
                    cout<<i<<' '<<lastOddPos<<endl;
            }
            else{
                if(a[i-1]%2)
                    cout<<i<<' '<<lastOddPos<<endl;
            }
            if(i==1) lastOddPos = 1;
        }
    }
    
    else{
        cout<<startEvenMoves<<endl;
        for(int i = 1; i<=n; i++){
            if(i%2==0){
                if(a[i-1]%2==0) cout<<i<<' '<<lastOddPos<<endl;
            }
            else{
                if(a[i-1]%2) cout<<i<<' '<<lastOddPos<<endl;
            }
            if(i==2) lastOddPos = 2;
        }
    }
}

int main() {
	int t;
	cin>>t;
	
	while(t--){
	    int n;
	    cin>>n;
	    
	    int odds = 0;
	    vector<int> a(n);
	    for(int i = 0; i<n; i++){
	        cin>>a[i];
	        if(a[i]%2) odds++;
	    }
	    
	    if(odds==0){
	        cout<<-1<<endl;
	    }
	    else{
	        generateMoves(a);
	    }
	}
	return 0;
}
3 Likes

Please clarify that,
If the two adjacent numbers are odd then their bitwise AND operation would make LSB 1 in result and their bitwise OR operation will also make LSB 1 in relation So, their Parity() value would be same.

Or

What if the whole sequence is odd?

This is my code.

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	int t;
	cin>>t;
	while(t--){
        int n,i,odd_0=0,even_0=0,odd_1=0,even_1=0;
        int oi=-1,ei=-1;
        cin>>n;
        int a[n];
        for(i=0;i<n;i++){
            cin>>a[i];
            if(oi==-1 && (a[i] & 1 == 1)){
                oi=i;
            }
            else if(ei==-1){
                ei=i;
            }
            if((a[i] & 1 == 1) && (i & 1 == 1)){
                odd_1++;
            }
            else if((a[i] & 1 == 1) && !(i & 1 == 1)){
                odd_0++;
            }
            else if(!(a[i] & 1 == 1) && !(i & 1 == 1)){
                even_0++;
            }
            else {
                even_1++;
            }
        }
        if((odd_0+odd_1==n) || (even_0+even_1==n)){
            cout<<-1<<'\n';
        }
        else{
            if(odd_0+even_1<even_0+odd_1){
                cout<<odd_0+even_1<<'\n';
                for(i=0;i<n;i+=2){
                    if(a[i] & 1 == 1){
                        cout<<i+1<<" "<<ei+1<<'\n';
                    }
                }
                for(i=1;i<n;i+=2){
                    if(!(a[i] & 1 == 1)){
                        cout<<i+1<<" "<<oi+1<<'\n';
                    }
                }
            }
            else{
                cout<<even_0+odd_1<<'\n';
                for(i=0;i<n;i+=2){
                    if(!(a[i] & 1 == 1)){
                        cout<<i+1<<" "<<oi+1<<'\n';
                    }
                }
                for(i=1;i<n;i+=2){
                    if((a[i] & 1 == 1)){
                        cout<<i+1<<" "<<ei+1<<'\n';
                    }
                }
            }
        }
    }
    return 0;
}

If both are odd, their LSB is 1. So, 1 \& 1 = 1 and 1 | 1=1 .

1 Like

I did everything that has been said in the editorial still the wrong answer. Here is my submission, Submission. Pls tell me where is it failing. Plus I don’t understand why does codechef not show the test cases where is it failing.

Here is my simplified python approach with minimal code… Here

And it should not be present in answer right?

I think here if all the elements of the array are odd, our sequence is not valid. To make it valid , we can take any other element and use it to toggle the parity of the number which we want ( 1 xor 1 = 0 ). and thus turn it into a sequence of alternating parity.

1 Like

Ok got it
Thanks.

Consider case-

1
5
0 0 0 0 1
3 Likes

what happens when 0 is in the cases as it is possible to have zero
i had an answer with this same approach but then because of zero i had to do it with numbers

there is no end to the corner cases, isn’t it?

This is not a corner case and there are no corner cases.

i m a beginner coder here(started 1 month back and have basic knowledge) and i tried to solve this bitblend problem my 1st method by which i submitted code was very long so i changed my approach and came with relatively short code than previous one.
i couldn’t find any testcase failing my code (Solution: 57948034 | CodeChef)

even testcase given below in replies are working right.
there is no TLE OR RE still i m unable to submit my code can anyone please help me and give me advice on my code???
its a request please help me considering ur junior your each piece of advice will be helpful for me.

My code is giving correct output for any input but it’s showing wrong in submission. Can somebody tell what’s wrong…

Here is my code-

https://www.codechef.com/viewsolution/57953915

wow

It Looks like you’re printing the moves incorrectly.

1 Like

I first checked the last odd element present in sequence and preassumed that its value can’t be changed as there is no further odd element present to satisfy the condition of the given question.

Then I created an ideal position
(Even odd even odd even …
Or
Odd-even-odd-even…) depending on where my last odd is present.

And print the output on the basis of the number of conflicts from the ideal case.
Please point out my mistake.

Here is my submission:

I also cross-checked this code on many self-created sample test cases…
It passes all those

I did my code according to the editorial, still the wrong answer. If anyone could debug my code or provide some corner test cases, I would be grateful. Here, is my code:

My Code

// Problem: Bitwise Blend
// Contest: CodeChef - February Long 2022 - I, Division 2 (Unrated)
// URL: Contest Page | CodeChef
// Memory Limit: 256 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define dd double
#define fio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ld long double
#define rep(i,a,b) for(ll i=a;i<b; i++)
#define ff first
#define ss second
#define mp make_pair
#define vl vector
#define mll map<ll,ll>
#define setbits(x) __builtin_popcountll(x)
#define zrbits(x) __builtin_ctzll(x)
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define ps(x,y) fixed<<setprecision(y)<<x
#define mk(arr,n,type) type *arr=new type[n];

const ll mod=1e9+7;

#define yes cout<<“YES\n”;
#define no cout<<“NO\n”;

void solve(){
ll n; cin>>n;
ll a[n], x;
rep(i,0,n){
cin>>x;
a[i]=x&1;
}
vector v;
vector<pair<ll,ll>> p,q;
ll d=0, e=0;
//101
rep(i,0,n){
if(i%2==0){
if(a[i]) v.pb(i);
else d++;
}
else{
if(a[i]){d++; v.pb(i);}
}
}
//010
rep(i,0,n){
if(i%2){
if(a[i]==0) e++;
}
else{
if(a[i]){e++;}
}
}
if(d==0 || e==0){cout<<0<<"\n"; return;}
if(v.size()==0){cout<<-1<<"\n";return;}
vector w=v;
stack r,s;
rep(i,0,n){
if(i%2==0){
if(a[i]==0){p.pb({i+1,v[0]+1}); v.pb(i);}
}
else{
if(a[i]){
if(i!=v[0]){p.pb({i+1,v[0]+1});}
else{
if(v.size()>1){p.pb({i+1,v[1]+1});}
else{r.push(i);}
}
}
}
}
rep(i,0,n){
if(i%2){
if(a[i]==0){q.pb({i+1,v[0]+1}); w.pb(i);}
}
else{
if(a[i]){
if(i!=w[0]){q.pb({i+1,w[0]+1});}
else{
if(w.size()>1){q.pb({i+1,w[1]+1});}
else{s.push(i);}
}
}
}
}
while(!r.empty()){
ll x=r.top(); r.pop();
p.pb({x+1,v[1]+1});
}
while(!s.empty()){
ll x=s.top(); s.pop();
q.pb({x+1,w[1]+1});
}
if(d<=e){
cout<<d<<"\n";
for(auto i:p) cout<<i.ff<<" “<<i.ss<<”\n";
}
else{
cout<<e<<"\n";
for(auto i:q) cout<<i.ff<<" “<<i.ss<<”\n";
}
}

int main(){
fio;
ll t=1; cin>>t;
while(t–){
solve();
}
return 0;
}

https://www.codechef.com/viewsolution/57896649
plz tell why this is not accepted