And-Or Game ORAND SOLUTION Code Chef

by

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

Subtasks

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

Example 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

Example Output

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 = []
    s.add(0)
    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:
                s.add(x|y)
                stack.append(x|y)
        for i in range(m):
            y = brr[i]
            if x&y not in s:
                s.add(x&y)
                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>();
h1.add(0);
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)){
h1.add(x|y);
s1.push(x|y);
}
}
for(int i=0;i<m;i++){
int y=b[i];
if(!h1.contains(x&y)){
h1.add(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;
    }
	
}

January Long Challenge 2021

Leave a Comment