Блог пользователя _thewiper_

Автор _thewiper_, история, 5 лет назад, По-английски

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.

  • Проголосовать: нравится
  • -17
  • Проголосовать: не нравится

»
5 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Can you share the problem link?

»
5 лет назад, скрыть # |
 
Проголосовать: нравится -9 Проголосовать: не нравится

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

  • »
    »
    5 лет назад, скрыть # ^ |
     
    Проголосовать: нравится +3 Проголосовать: не нравится

    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.

»
5 лет назад, скрыть # |
 
Проголосовать: нравится -41 Проголосовать: не нравится

You can use Trie Data Structure to solve this problem.

»
5 лет назад, скрыть # |
 
Проголосовать: нравится -17 Проголосовать: не нравится

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.

»
5 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

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

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +9 Проголосовать: не нравится

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

»
5 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

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.