Yuki726's blog

Help in bitwise OR problem!
By Yuki726, history, 4 years ago, In English

Find a pair in an array with maximum bitwise OR? $$$1 \leq n \leq 1e6, 0 \leq a[i] \leq 1e6$$$

Can anyone help me with the solution or finding a blog somewhere.

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

»
4 years ago, # |
← Rev. 6   Vote: I like it +5 Vote: I do not like it

Maybe we can use SOS DP. Idea ->

We apply SOS DP to find array B, where B[i] represents the maximum masked value present in the given array where (value & i) == i.

Now, We again apply SOS to find array C, where C[i] represents the maximum values of B[i] among all the sub mask of C[i]. now to get maximum or with A[i], we complement it and get the corresponding answer from C[~A[i]].

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Yuki726 I know the explanation is weird. But look at the code below, it's simple. Let me know if it is failing or if I am wrong somewhere. Code

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

      Same approach has been mentioned in Maxor editorial. So probably your approach is correct (I tested with brute force too). But I am unable to prove it.

      → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      Thanks for the reply. Your code is correct and I was finally able to prove it.

      → Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    nvm

    → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Check this out ...

problem:- https://www.codechef.com/problems/MAXOR

editorial:- https://discuss.codechef.com/t/maxor-ediorial/15798

→ Reply