Please read the new rule regarding the restriction on the use of AI tools. ×
Rating changes for last rounds are temporarily rolled back. They will be returned soon. ×

_thewiper_'s blog

By _thewiper_, history, 3 years ago, In English

eleph_2323 1m Can someone help me in the following problem Given an array consisting of n integers and q queries. And in each query there is an integer x for which you need to report that is there any number in the array such that its bitwise and with x is zero. 1<=N,Q<=10^5,1<=arr[i]<=10^9

I tried doing this problem using Trie but couldn’t get the most optimised solution. Can someone help.

  • Vote: I like it
  • -17
  • Vote: I do not like it

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

Can you share the problem link?

»
3 years ago, # |
  Vote: I like it -9 Vote: I do not like it

Firstly we can find the bitwise-OR of all elements(say ORall) in the array and for every set bit in ORall the array, we can store one element which has this bit set. And for every query, if (q=x&ORall>0 we can find the element corresponding to any set bit in q). I think this can work

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

    I don't think this will work because let's say x is 110010=50 So in array we need to find a number whose 2nd,5th and 6th bit should have 0.Now there can be multiple elements whose one specific bit is not set So we need to take intersection of elements whose 2nd,5th and 6th bit is not set This will result in O(n) time per query which will give tle.

»
3 years ago, # |
  Vote: I like it -41 Vote: I do not like it

You can use Trie Data Structure to solve this problem.

»
3 years ago, # |
  Vote: I like it -17 Vote: I do not like it

This is a variation of this question and can be easily solved using Trie. You just have to think about what changes should be made to handle AND instead of XOR.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    They are absolutely unrelated.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Sorry, if you find it unrelated but I have solved only this problem related to this xor-trie concept and I was able to figure out the fully accepted solution to above mentioned problem in the blog in my google coding round.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Are you sure that $$$arr[i] \leq 10^9$$$ ? The exact problem(except constraints on $$$arr[i]$$$) has been discussed here.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Sorry i wrote constraints on A[i] .And yes the questions are same as in the blog

»
3 years ago, # |
  Vote: I like it +9 Vote: I do not like it

If $$$arr[i]<=10^6$$$ then this problem is same as this one https://codeforces.me/contest/165/problem/E .Not quite sure if preprocessing can be done for values upto $$$10^9$$$

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

This question has surfaced many times in a past few days, this problem can be solved using SOS DP easily. The link for the codeforces blog on SOS DP is available easily, just google SOS DP.

for the solution, here is the code that I wrote.

Code

Please mind the template, it is a bit cluttered.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Are you sure?

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

      Yes I also used SOS dp and all it passed all the test cases.

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

        How is that possible with arr[i]<=1e9?

        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          oh sorry I didn't saw the constraints given in the blog ...in the test it was ai<=1e5

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    but if a[i]<1e9 how can it pass considering O(2^32)

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

      Ohh! Missed it, actually in the original question ai also had a range of 1e5 instead of 1e9

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Really thanks sir but how to solve if a[i] is actually upto 1e9

        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Then I guess our last resort will be using a trie.