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

Help in bitwise OR problem!
Автор Yuki726, история, 5 лет назад, По-английски

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

»
5 лет назад, # |
← 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]].

→ Ответить
»
5 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Check this out ...

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

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

→ Ответить