Bitwise Blend Solution Codechef

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,…,ANA1,A2,…,AN tasty if it satisfies the following condition:

  • parity(Ai&Ai+1)≠parity(Ai|Ai+1)parity(Ai&Ai+1)≠parity(Ai|Ai+1) for 1≤i<N1≤i<N.

Chef gives you a sequence A1,A2,…,ANA1,A2,…,AN. You may perform the following operation on the sequence any number of times (possibly 00):

  • Choose 22 indices ii and jj (1≤i,j≤n1≤i,j≤n ; i≠ji≠j) and change AiAi to Ai⊕AjAi⊕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,

Input Format

  • The first line of the input contains a single integer TT denoting the number of test cases. The description of TT test cases follows.
  • The first line of each test case contains a single integer NN.
  • The second line contains NN space-separated integers A1,A2,…,ANA1,A2,…,AN.

Output Format

For each test case:

  • If it is impossible to convert the given sequence into a tasty sequence using the given operations, print a single line containing the integer −1−1.
  • Otherwise, first, print a line containing a single integer MM ― the minimum number of operations you have to perform.
  • Then, print MM lines describing these operations in the order in which you want to perform them. For each kk (1≤k≤M1≤k≤M), the kk-th of these lines should contain two space-separated integers ii and jj (1≤i,j≤n1≤i,j≤n ; i≠ji≠j) ― the indices on which the kk-th operation is performed.

If there are multiple solutions, you may find any one of them.

Constraints

  • 1≤T≤3⋅1031≤T≤3⋅103
  • 2≤N≤1052≤N≤105
  • 0≤Ai<2300≤Ai<230 for each valid ii
  • The sum of NN over all test cases does not exceed 2⋅1052⋅105

Subtasks

Subtask #1 (100 points): Original constraints

Sample Input 1 

2
2
0 0
3
6 16 69

Sample Output 1 

-1
1
1 3

Explanation

Test case 11: It is impossible to make AA tasty using the given operations.

Test case 22: We can choose i=1i=1 and j=3j=3 and apply the operation which converts AA into [67,16,69][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);
             
             }  

            }
             }
          }
        

           
        }

February Long Challenge 2022 Solution

January Long Challenge 2022 Solution

Leave a Comment

13 − twelve =