Bitwise Blend Solution Codechef
Chef loves bitwise operations. So, he creates the following problem but needs your help to solve it.
Chef calls a sequence of integers A1,A2,…,A tasty if it satisfies the following condition:
- parity(Ai&Ai+1)≠parity(Ai|Ai+1) for 1≤i<N.
Chef gives you a sequence A1,A2,…,AN. You may perform the following operation on the sequence any number of times (possibly 0):
- Choose 2 indices ii and jj (1≤i,j≤n ; i≠j) and change Ai to Ai⊕Aj.
Chef is asking you to make the sequence tasty using the minimum number of operations, or report that it is impossible.
As a friendly reminder,
- parity(x) denotes the remainder of dividing x by 2
- & denotes the bitwise AND operation
- | denotes the bitwise OR operation
- ⊕ denotes the bitwise XOR operation.
Input Format
- The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
- The first line of each test case contains a single integer N.
- The second line contains N space-separated integers A1,A2,…,AN.
Output Format
For each test case:
- If it is impossible to convert the given sequence into a
tastysequence using the given operations, print a single line containing the integer −1. - Otherwise, first, print a line containing a single integer M the minimum number of operations you have to perform.
- Then, print M lines describing these operations in the order in which you want to perform them. For each kk (1≤k≤M), the kk-th of these lines should contain two space-separated integers i and j (1≤i,j≤n ; i≠j) the indices on which the k-th operation is performed.
If there are multiple solutions, you may find any one of them.
Constraints
- 1≤T≤3⋅103
- 2≤N≤105
- 0≤Ai<230 for each valid i
- The sum of N over all test cases does not exceed 2⋅105
Subtasks
Subtask #1 (100 points): Original constraints
Sample Input 1
2
2
0 0
3
6 16 69Sample Output 1
-1
1
1 3Explanation
Test case 1: It is impossible to make A tasty using the given operations.
Test case 2: We can choose i=1 and j=3 and apply the operation which converts A into [67,16,69] which is tasty.
SOLUTION
Program: Bitwise Blend Solution in Python
for _ in range(int(input())):
l=int(input())
seq=[int(i)%2 for i in input().split()]
if not any(seq):
print(-1)
else:
count=[[],[]]
k=0
for i in range(l):
count[k%2].append(i)
if i<l-1 and seq[i]==seq[i+1]:
k+=1
min=count[0] if len(count[0])<=len(count[1]) else count[1]
print(len(min))
for i in min:
seq[i]=-1
print(i+1,1+seq.index(1))Program: Bitwise Blend Solution in C++
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin>>t;
while(t--){
int n;
cin>>n;
long long int a[n];
int flag=0;
for(int i=0;i<n;i++){
cin>>a[i];
if(a[i]%2!=0)
flag=1;
}
if(flag==0)
cout<<"-1"<<endl;
else{
int count1=0,count2=0;
for(int i=0;i<n;i++){
if(i%2==0)
if(a[i]%2)
count1++;
else
count2++;
else
if(a[i]%2)
count2++;
else
count1++;
}
int m=min(count1,count2);
if(count2==m){
cout<<m<<endl;
int temp=0;
for(int i=0;i<n;i=i+2)
if(a[i]%2){
temp=i;
break;
}
for(int i=0;i<n;i++)
if(i%2==0){
if(a[i]%2==0)
cout<<i+1<<" "<<temp+1<<endl;
}
else{
if(a[i]%2)
cout<<i+1<<" "<<temp+1<<endl;
}
}
else{
cout<<m<<endl;
int temp=0;
for(int i=1;i<n;i=i+2)
if(a[i]%2){
temp=i;
break;
}
for(int i=0;i<n;i++)
if(i%2==0){
if(a[i]%2)
cout<<i+1<<" "<<temp+1<<endl;
}
else{
if(a[i]%2==0)
cout<<i+1<<" "<<temp+1<<endl;
}
}
}
}
return 0;
}Program: Bitwise Blend Solution in Java
import java.util.*;
import java.io.*;
class Codechef {
public static void main(String[] args) throws java.lang.Exception {
Scanner sc = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
int t = sc.nextInt();
while (t-- > 0)
{
int n=sc.nextInt();
int arr[]= new int[n];int count=0;int s=1;int odd1=-1,odd2=-1;
ArrayList<Integer> l1 = new ArrayList<Integer>();
ArrayList<Integer> l2 = new ArrayList<Integer>();
for(int i=0;i<n;i++)
{
arr[i]=sc.nextInt();
if(arr[i]%2!=0)
{count=count+1;
if(i%2==0&&odd1==-1)
{
odd1=i+1;
}
if(i%2!=0&&odd2==-1)
{
odd2=i+1;
}
}
if(arr[i]%2==s)
{
l2.add(i);
}
else
{
l1.add(i);
}
if(s==0)
{
s=1;
}
else
{
s=0;
}
}
int a=l1.size();
int b=l2.size();
if(count==0)
{
System.out.println(-1);
}
else if(a==0||b==0)
{
System.out.println(0);
}
else if(a<b)
{
System.out.println(a);
for (int i = 0; i < l1.size(); i++)
{
System.out.println((l1.get(i)+1)+" "+odd1);
}
}
else
{
System.out.println(b);
for (int i = 0; i < l2.size(); i++)
{
System.out.println((l2.get(i)+1)+" "+odd2);
}
}
}
}
}