# And-Or Game ORAND SOLUTION Code Chef

Page Contents

## And-Or Game ORAND SOLUTION Code Chef

Chef is playing a game with two sequences of non-negative integers A1,A2,…,ANA1,A2,…,AN and B1,B2,…,BMB1,B2,…,BM. He has an integer VV, which is initially equal to 00. Chef will play for a number of turns he chooses (possibly zero); he stops playing when he gets bored. In each turn of the game, Chef must perform one of the following operations:

• Choose an integer XX from AA and change VV to V∨XV∨X, i.e. the bitwise OR of VV and XX.
• Choose an integer XX from BB and change VV to V∧XV∧X, i.e. the bitwise AND of VV and XX.

Find the number of possible distinct values which VV can have after the game ends.

### Input

• 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 two space-separated integers NN and MM.
• The second line contains NN space-separated integers A1,A2,…,ANA1,A2,…,AN.
• The third line contains MM space-separated integers B1,B2,…,BMB1,B2,…,BM.

### Output

For each test case, print a single line containing one integer ― the number of possible values of VV after the game ends.

### Constraints

• 1≤N,M≤2201≤N,M≤220
• 0≤Ai<2200≤Ai<220 for each valid ii
• 0≤Bi<2200≤Bi<220 for each valid ii
• A1,A2,…,ANA1,A2,…,AN are pairwise distinct
• B1,B2,…,BMB1,B2,…,BM are pairwise distinct
• the sum of NN over all test cases does not exceed 220220
• the sum of MM over all test cases does not exceed 220220

Subtask #1 (30 points, time limit 2 seconds):

• 1≤N,M≤2101≤N,M≤210
• 0≤Ai<2100≤Ai<210 for each valid ii
• 0≤Bi<2100≤Bi<210 for each valid ii

Subtask #2 (30 points, time limit 2 seconds):

• 1≤N,M≤2151≤N,M≤215
• 0≤Ai<2150≤Ai<215 for each valid ii
• 0≤Bi<2150≤Bi<215 for each valid ii

Subtask #3 (40 points, time limit 5 seconds): original constraints

```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
```

```6
9
8
```

### Explanation

Example case 1: VV can reach the values {0,5,12,13,14,15}{0,5,12,13,14,15}.

Example case 2: VV can reach the values {0,1,3,6,7,12,13,14,15}{0,1,3,6,7,12,13,14,15}.

Example case 3: VV can reach the values {0,1,2,3,4,5,6,7}{0,1,2,3,4,5,6,7}.

## Solution

Program Python:

```t = int(input())
while t:
n,m = map(int,input().split(" "))
s = set()
stack = []
stack.append(0)
arr = list(map(int,input().split(" ")))
brr = list(map(int,input().split(" ")))
while stack:
x=stack.pop()
for i in range(n):
y = arr[i]
if x|y not in s:
stack.append(x|y)
for i in range(m):
y = brr[i]
if x&y not in s:
stack.append(x&y)
print(len(s))

t-=1```

Program Java:

```import java.util.*;
import java.lang.*;
import java.io.*;

class Codechef
{

public static void main (String[] args) throws java.lang.Exception
{
Scanner scan=new Scanner(System.in);
int t=scan.nextInt();
while(t-- !=0){
int n=scan.nextInt();
int m=scan.nextInt();
TreeSet<Integer> h1=new TreeSet<Integer>();
Stack<Integer> s1=new Stack<Integer>();
s1.push(0);
int a[]=new int[n];
int b[]=new int[m];
for(int i=0;i<n;i++){
a[i]=scan.nextInt();
}
for(int i=0;i<m;i++){
b[i]=scan.nextInt();
}
while(!s1.isEmpty()){
int x=(int)(s1.pop());
for(int i=0;i<n;i++){
int y=a[i];
if(!h1.contains(x|y)){
s1.push(x|y);
}
}
for(int i=0;i<m;i++){
int y=b[i];
if(!h1.contains(x&y)){
s1.push(x&y);
}
}
}

System.out.println(h1.size());
}
}
}```

Program C++:

```#include <iostream>
#include<bits/stdc++.h>
using namespace std;

int main() {
long long t;
cin>>t;
while(t--)
{
long long n,m;
cin>>n>>m;
long long *A=new long long[n];
long long *B=new long long[m];
stack<long long> s1 ;
vector<long long> v1;
//find(v1.begin(),v1.end,item)!=v1.end();
v1.push_back(0);
s1.push(0);
for(long long i=0;i<n;i++)
cin>>A[i];
for(long long i=0;i<m;i++)
cin>>B[i];
while(!s1.empty()){
long long x=int(s1.top());
s1.pop();
for(long long i=0;i<n;i++){
int y=A[i];
if((find(v1.begin(),v1.end(),x|y)==v1.end())){
v1.push_back(x|y);
s1.push(x|y);
}
}
for(long long j=0;j<m;j++){
long long y=B[j];
if((find(v1.begin(),v1.end(),x&y)==v1.end())){
v1.push_back(x&y);
s1.push(x&y);
}
}

}
cout<<v1.size()<<endl;
}

}```