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.
№ | Пользователь | Рейтинг |
---|---|---|
1 | ecnerwala | 3648 |
2 | Benq | 3580 |
3 | orzdevinwang | 3570 |
4 | cnnfls_csy | 3569 |
5 | Geothermal | 3568 |
6 | tourist | 3565 |
7 | maroonrk | 3530 |
8 | Radewoosh | 3520 |
9 | Um_nik | 3481 |
10 | jiangly | 3467 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | maomao90 | 174 |
2 | awoo | 164 |
2 | adamant | 164 |
4 | TheScrasse | 159 |
4 | nor | 159 |
6 | maroonrk | 156 |
7 | -is-this-fft- | 150 |
8 | SecondThread | 147 |
9 | orz | 146 |
10 | pajenegod | 145 |
Название |
---|
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]].
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
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.
Thanks for the reply. Your code is correct and I was finally able to prove it.
Welcome!
nvm
Check this out ...
problem:- https://www.codechef.com/problems/MAXOR
editorial:- https://discuss.codechef.com/t/maxor-ediorial/15798