Help me in solving ALIENOR problem

help
,
1

My issue

I’m not understanding the question.
Is it really that difficult to comprehend?
Please someone explain it to me. please

Problem Link: ALIEN-OR Practice Coding Problem - CodeChef

2

It’s not a hard question, but you need to have some background. This is a Bit Manipulation problem:
Bit manipulation Programming Practice Problem Course Online - CodeChef

  • You are given an N amount of numbers whose binary length is K

E.g.:
N = 5
K = 3

N1. 000
N2. 001
N3. 010
N4. 111
N5. 100

  • Your task is to determinate if you can build any number in the set [1, 2^K) by taking a subset of N and applying the bitwise OR operation to that subset

First, what numbers are in the set [1,2^K)?
If K = 3, then 2^K is 8
So:
1,2,3,4,5,6,7

Second, take a subset of N and apply the bitwise OR to build the numbers from 1 to 7
1 = ( N2 )
2 = ( N3 )
3 = ( N2 | N3 )
4 = ( N5 )
5 = ( N5 | N2 )
6 = ( N5 | N3 )
7 = ( N5 | N3 | N2 )

I can build any number from 1 to 2^K in that example, so the answer is yes.
We could know whether it’s possible or not by checking if there were all the powers of 2 from 1 to K in N

This was my solution:

#include <bits/stdc++.h> 
#define ll long long 
using namespace std; 

void solve(){ 

    ll N,K;
    cin >> N >> K;
    
    // Input the numbers in a set for
    // easier serch
    unordered_set<string> A(N);
    string input;
    for(ll i=0; i<N; i++){
        cin >> input;
        A.insert(input);
    }
    
    // Create a vector with the needed
    // numbers (binary powers of 2 from 1 to K)
    vector<string> needed(K);
    for(ll i=0; i<K; i++){
        string local = "";
        for(ll j=0; j<K; j++){
            local += "0";
        }
        local[i] = '1';
        needed[i] = local;
    }
    
    // Look for the needed numbers
    bool possible = true;
    for(auto n : needed){
        if(A.find(n) == A.end()){
            possible = false;
            break;
        }
    }

    if (possible){
        cout << "YES\n";
    }
    else{
        cout << "NO\n";
    }

} 

int main() { 
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL); 
    cout.tie(NULL); 
    int T; 
 
    cin >> T; 
    while(T--){ 
        solve(); 
    } 
}
1 Like
3

Thank you very much
I understood the question.
First I’ll try then if I get stuck again I’ll refer to your solution.
Once again thank you

1 Like