FameOfTheLegends's blog

By FameOfTheLegends, history, 2 months ago, In English

given an array with n elements, and Q queries consisting of an integer find whether there exists an element in the array such that it's bitwise and is zero

1<=n<10^5 , 1<=q<10^5.

Can anyone tell how to do this question.

 
 
 
 
  • Vote: I like it
  • +8
  • Vote: I do not like it

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Is there a constraint on how big the elements can be?

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Since the query number is at most 10^5, any number greater than 10^5 can have its most significant bits removed till it's smaller than 10^5 without affecting the answer. So we can assume that the input array numbers too would be smaller than 10^5 (or can be made so)

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Here you go!

»
2 months ago, # |
Rev. 3   Vote: I like it -19 Vote: I do not like it

You can use Binary Tries.

Create a Trie with the given array elements and then traverse the trie in accordance with the element given in the query (let x).

If the ith bit of x is 1, see if the trie contains 0 for corresponding bit, and, if the ith bit of x is 0, just continue traversing trie.

let m be the maximum element in the given array. Overall Time complexity : O((n+q)logm)

Feel free to Correct me if I am wrong.

  • »
    »
    2 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    I think in worst case (x=0), you will have to go through the whole Trie which will be 2^(No of bits). That will be O(q*2^(No of bits)) for queries.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How you guys are making sure if his contest is over now?

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    the contest is from 12 pm to 4 pm from 9 july. Also these previusly asked question from my friends.

»
2 months ago, # |
Rev. 3   Vote: I like it +5 Vote: I do not like it

Alright, I'll try to describe the solution that I have in mind to the best of my ability. If you do not understand please feel free to ask any doubts. I assume that there are no duplicate numbers in the input, if there are then they can be safely ignored since they do not provide any value

Let the input numbers in the array be a1, a2, and so on...

Let us consider a single query q.

The task is to specify whether there exists any a1 such that a1^q = 0

Let the one's complement of a1 be a1'.

Then the two following 2 conditions are equivalent

a1^q = 0 and a1'^q = q

So, if we were to store a1' in our array instead of a1, then the query would change to finding the existence of a number such that it has all the bits set at the given bits of q.

Since the input numbers can only be as large as 10^5, we only need to concern ourselves with 17 bits.

We can solve the modified problem by creating a bitset array that stores the answer for that number.

To do this we initialize an array of size 1<<17 to all false. For all the numbers in the array, we find all its subsets and set them to true.

This step takes almost 3^17 time (refer here for details — https://cp-algorithms.com/algebra/all-submasks.html)

Now, for each query, just output the value at your constructed bitset array!

»
2 months ago, # |
  Vote: I like it +6 Vote: I do not like it

There exists $$$O(MAX(a_i) \log MAX(a_i))$$$ using SOS dp.

For a given mask, we want to compute the number of elements in the array that are a submask to it. Then, to answer a query $$$x$$$, we just check if $$$freq[\sim x]$$$ is non-zero.

Run a SOS dp to do this and it takes above time complexity.

AFAIK this is the same problem as the one you're asking: https://codeforces.com/contest/165/problem/E. You can look at the editorial there if you need more explanation.