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
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
- Chef and Division 3 DIVTHREE SOLUTION Code Chef
- Encoded String DECODEIT SOLUTION Code Chef
- Point Of Impact BILLRD SOLUTION Code Chef
- Fair Elections FAIRELCT SOLUTION Code Chef
- Watching CPL WIPL SOLUTION Code Chef
- Chef and Ants ANTSCHEF SOLUTION Code Chef
- Blackjack BLKJK SOLUTION Code Chef
- And-Or Game ORAND SOLUTION Code Chef
- Stack-Queue Sort (Challenge) SQSORT SOLUTION Code Chef
- Expected Number of SCCs RCTEXSCC SOLUTION Code Chef
- Curious Matrix CURMAT SOLUTION Code Chef
- Cool Subsets COOLSBST SOLUTION Code Chef
- Sequence Creation ARCRT SOLUTION Code Chef
- Greedy Students GRDSTD SOLUTION Code Chef