[Solved] Magical Flips codechef solution

Magical Flips codechef solution

Chef found NN magical cards in his drawer. Each card has a number written on each of its faces. He places all the cards on the table in a front face-up manner.

Chef denotes the numbers on the front face by A1,A2,...,ANA1,A2,…,AN and on the back face by B1,B2,...,BNB1,B2,…,BN. Chef can choose some (possibly zero or all) cards and flip them, then he will calculate the bitwise AND of all the numbers currently in a face-up manner.

Now Chef wonders what is the maximum bitwise AND that he can achieve and what is the minimum number of cards he has to flip to achieve this value. Can you help him find it?

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.
  • Each test case contains three lines of input.
  • The first line contains a single integer NN – the number of cards.
  • The second line contains NN space-separated integers A1,A2,...,ANA1,A2,…,AN – the numbers on the front face of the cards
  • The third line contains NN space-separated integers B1,B2,...,BNB1,B2,…,BN – the numbers on the back face of the cards

Output Format

For each test case, print a single line containing two space-separated integers, first denoting the maximum bitwise AND possible and second denoting the minimum number of flips required to achieve it.

Constraints

  • 1T1041≤T≤104
  • 1N1051≤N≤105
  • 0Ai23010≤Ai≤230−1
  • 0Bi23010≤Bi≤230−1
  • Sum of NN over all testcases does not exceeds 105105.

Sample Input 1 

3
3
4 6 8
2 1 2
3
0 2 0
2 0 8
3
1 2 1
2 3 6

Sample Output 1 

2 2
0 0
2 2

Explanation

Test case 11: The maximum AND is obtained after flipping the first and third cards achieving a configuration of [2,6,2][2,6,2] which yields a bitwise AND of 22.

Test case 22: Every possible configuration of the cards yields a bitwise AND equal to 00. So to ensure the minimum number of operations, Chef performs no flip.


Solution


Python

t = int(input())
for xyz in range(t):
n = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
m = max(max(A), max(B))
b = 0
while m > 1:
m = m // 2
b += 1
ans = 0
flips = 0
while b >= 0:
f = True
for i in range(n):
if (((A[i]>>b)&1) == 0 or (ans & A[i]) != ans) and (B[i] == None or ((B[i]>>b)&1) == 0 or (ans & B[i]) != ans):
f = False
break
if f:
cur = 0
for i in range(n):
if ((A[i]>>b)&1) == 0 and B[i] != None:
A[i] = B[i]
B[i] = None
cur += 1
flips += cur
ans += (1<<b)
b -= 1
print(ans, flips)


Java

 

import java.util.*;

class Codechef
{
public static void main(String[] args) {
Scanner s= new Scanner(System.in);
int t=s.nextInt();
while(t–>0)
{
int n=s.nextInt();
int ans=0,mn=0;
int arr1[]= new int[n];
int arr2[]=new int[n];
for(int i=0;i<n;i++)
arr1[i]=s.nextInt();
for(int i=0;i<n;i++)
arr2[i]=s.nextInt();
int inverted[]= new int[n];
for(int i=0;i<n;i++)
inverted[i]=-1;

for(int i = 29; i >= 0; i–) {
int isPossible = 1;
for(int j = 0; j < n; j++) {
if(inverted[j] != -1) {
if(inverted[j] == 1) isPossible = ((isPossible&(arr2[j]>>i)&1));
else isPossible = ((isPossible&(arr1[j]>>i)&1));
continue;
}
if(((arr1[j]>>i)&1)==1 || ((arr2[j]>>i)&1)==1) {}
else {
isPossible = 0;
break;
}
}
if(isPossible==0)
continue;
int val = 1;
for(int j = 0; j < n; j++) {
if(inverted[j] != -1) {
if(inverted[j] == 1) val = ((val&(arr2[j]>>i)&1));
else val = ((val&(arr1[j]>>i)&1));
continue;
}
if(((arr1[j]>>i)&1)==1 && ((arr2[j]>>i)&1)==1) {}
else if(((arr1[j]>>i)&1)==1) inverted[j] = 0;
else if(((arr2[j]>>i)&1)==1) {inverted[j]= 1; mn++;}
else {
val = 0;
break;
}
}
ans += (val * (1<<i));
}
System.out.println(ans+” “+mn);

}
}

}


C++

#include<bits/stdc++.h>
using namespace std;
void solve() {
int n, ans = 0, mn = 0;
cin >> n;
vector<int> a(n), b(n);
for(int i = 0; i < n; i++)
cin >> a[i];
for(int i = 0; i < n; i++)
cin >> b[i];
vector<int> inverted(n, -1);
for(int i = 29; i >= 0; i–) {
int isPossible = 1;
for(int j = 0; j < n; j++) {
if(inverted[j] != -1) {
if(inverted[j] == 1) isPossible = ((isPossible&(b[j]>>i)&1));
else isPossible = ((isPossible&(a[j]>>i)&1));
continue;
}
if(((a[j]>>i)&1) || ((b[j]>>i)&1)) {}
else {
isPossible = 0;
break;
}
}
if(!isPossible)
continue;
int val = 1;
for(int j = 0; j < n; j++) {
if(inverted[j] != -1) {
if(inverted[j] == 1) val = ((val&(b[j]>>i)&1));
else val = ((val&(a[j]>>i)&1));
continue;
}
if(((a[j]>>i)&1) && ((b[j]>>i)&1)) {}
else if(((a[j]>>i)&1)) inverted[j] = 0;
else if(((b[j]>>i)&1)) inverted[j] = 1, mn++;
else {
val = 0;
break;
}
}
ans += (val * (1ll<<i));
}
cout << ans << ” ” << mn << ‘\n’;
}

int main() {
// your code goes here
int t;
cin>>t;
while(t–){
solve();
}
return 0;
}


Also read : Black cells in a chessboard solution codechef

Also read : Large Square solution codechef

Also read : Bus full of passengers solution codechef

Also read : Friend Groups In A Line solution codechef 

Magical Flips codechef solution


Also read :  Polycarp and String Transformation solution codeforces

Leave a Comment

Your email address will not be published. Required fields are marked *