Пожалуйста, прочтите новое правило об ограничении использования AI-инструментов. ×
Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены. ×

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

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

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
  • Проголосовать: не нравится

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

Can you share the problem link?

»
3 года назад, # |
  Проголосовать: нравится -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

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +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.

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

You can use Trie Data Structure to solve this problem.

»
3 года назад, # |
  Проголосовать: нравится -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.

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

    They are absolutely unrelated.

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

      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 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

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

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 года назад, # |
  Проголосовать: нравится 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.