FFT of bitwise OR?

Revision en1, by lixolas, 2017-10-18 22:50:15

Hello everyone!

I was competing at CS Academy earlier today. After some time, I started to think about problem E (link is here: http://csacademy.com/contest/round-53/task/maxor/). The problem is basically to find the maximum bitwise OR operation of 2 elements in the array, and how many pair of elements have this value. I figured out a different solution of the editorial: we can make an FFT multiplication of the array, but instead of multiplication we use the OR operation. This could give the answer. But I searched for it on the internet and found nothing about this FFT. I thought it was worth asking here: have anyone of you heard about FFT of bitwise OR?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English lixolas 2017-10-18 22:50:15 736 Initial revision (published)