And-Or Game ORAND SOLUTION Code Chef

And-Or Game ORAND SOLUTION Code Chef

And-Or Game ORAND SOLUTION  Chef is bored so he decided to play a game with two sets of numbers A and B of sizes N and M and an integer V initially equal to 0. Chef will play for a number of turns (possibly zero). Every turn in this game Chef will do one of the following operations:

 

Pick an integer X from the set A and assign V with V|X i.e the bitwise oring of the two numbers.And-Or Game ORAND SOLUTION
Pick an integer X from the set B and assign V with V&X i.e the bitwise anding of the two numbers.
Chef will stop playing when he gets bored. Find the number of values V can become when the game ends.
 
Input:
  • First line will contain T, number of testcases. Then the testcases follow.
  • The first line of each test case contains 2 space-separated integers, N and M.
  • The second line contains N integers, A1, A2, …, AN
  • The third line contains M integers, B1, B2, …, BM
Output:
For each test case, Print the number of values V can become.
 
Constraints
  • 1≤N,M≤220
  • 0≤Ai,Bi<220
  • The sum of N over all cases in a subtask doesn’t exceed 220.
  • The sum of M over all cases in a subtask doesn’t exceed 220.
  • The elements in A are pairwise distinct.
  • The elements in B are pairwise distinct.
Subtasks
  • 30 points (time limit 2s): 1≤N,M≤210 and 0≤Ai,Bi<210.
  • 30 points (time limit 2s): 1≤N,M≤215 and 0≤Ai,Bi<215.
  • 40 points (time limit 5s): 1≤N,M≤220 and 0≤Ai,Bi<220.
Sample Input:
3
3 1
5 12 14
15
6 1
0 1 3 6 12 14
1
4 3
1 3 5 6
3 6 10
Sample Output:
6
9
8
EXPLANATION:
  • In the first test case, V can reach values [0,5,12,13,14,15].
  • In the second test case, V can reach values [0,1,3,6,7,12,13,14,15].
  • In the third test case, V can reach values [01,2,3,4,5,6,7].

5 thoughts on “And-Or Game ORAND SOLUTION Code Chef”

Leave a Comment

close
error: Content is protected !!