Magical Flips solution codechef

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 Magical Flips solution codechef

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 Magical Flips solution codechef

  • 1≤T≤1041≤T≤104
  • 1≤N≤1051≤N≤105
  • 0≤Ai≤230−10≤Ai≤230−1
  • 0≤Bi≤230−10≤Bi≤230−1
  • Sum of NN over all testcases does not exceeds 105105.

Sample Input 1  Magical Flips solution codechef

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 Magical Flips solution codechef

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.

Chef and Professor solution codechef- python, java, c++

DIY Tree solution codeforces

Gates to Another World solution codeforces

Leave a Comment