FifthThread's blog

Google Online Assesment Question
By FifthThread, history, 3 years 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

Comments Comments (8)
| Write comment?
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    3 years 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)

    → Reply
»
3 years 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!

→ Reply
»
3 years 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.net/contest/165/problem/E. You can look at the editorial there if you need more explanation.

→ Reply