And-Or Game ORAND SOLUTION Code Chef

Page Contents

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 1

5 12 14

6 1

0 1 3 6 12 14

4 3

1 3 5 6

3 6 10

Sample Output:

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].

CLICK HERE

Please Click HERE

And-Or Game ORAND SOLUTION Code Chef

And-Or Game ORAND SOLUTION Code Chef

January Long Challenge 2021

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

Leave a Comment Cancel reply