Yuki726's blog

By Yuki726, history, 2 years ago,

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.

• +16

 » 2 years ago, # | ← Rev. 6 →   +5 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]].
•  » » 2 years ago, # ^ |   +8 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
•  » » » 2 years ago, # ^ |   0 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.
•  » » » 2 years ago, # ^ |   +8 Thanks for the reply. Your code is correct and I was finally able to prove it.
•  » » » » 2 years ago, # ^ |   0 Welcome!
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 nvm
 » 2 years ago, # | ← Rev. 2 →   0 Check this out ...