lixolas's blog

FFT of bitwise OR?
By lixolas, history, 7 years ago, In English

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?

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

»
7 years ago, # |
  Vote: I like it +25 Vote: I do not like it

Click

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

    Is there any generalized way to find 2x2 Walsh-Hadamard Matrix (for any other boolean operation or other kind operation) ?

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

    Really thanks!! Did not found this before. I will try solving the problem again later. Thanks again =)

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

    This is so useful. Thanks. MazzForces

    → Reply
»
7 years ago, # |
  Vote: I like it +5 Vote: I do not like it

As that link above suggests it is a well known transformation, I solved it that way as well. That being said, could you explain how you figured out the way to get the exact transformation? Just out of curiosity :P

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

    Sure! :P First, I supposed that the problem asked for the greatest sum, and how many pairs have that sum. It is a really simple problem, we just have to get the two higher values and count how many times they apear in the original array. However, it can also be solved using FFT: we call the array a polynomial, then we take the square of it. Now, if there was some transformation that the final polynomial stored at the coefficient of x^n how many values had OR n (instead of sum n), it would be great, since the value we want would be index of the last coefficient greater than 0, and the number of pairs that have this OR is exactly this coefficient (or it divided by 2, not really sure :P). So, since FFT solved the first problem, I thought that by some changes it could also solve the other one (since I've heard before about XOR FFT).

    → Reply