s3ct4l-r3x's blog

XOR path (ACM ICPC dhaka regionals 2017)
By s3ct4l-r3x, history, 7 years ago, In English

This question appeared in icpc regionals dhaka 2017. Click here for the question.

My approach to solve the problem is to traverse the tree once using DFS considering any node as the root and maintaining the xor distance along a path from the root. Since the edge weights cant exceed 2^16-1, every xor distance can be hashed in an array storing its frequency as the value.

Now the problem reduces to finding pairs of numbers whose xor is equal to x, for all 0<=x<=2^16-1. Let say the pair of numbers are a and b. Then if a ⊕ b= x, then x ⊕ a = b. Hence for every a present in the hashmap frequency of b can be found and finding the count of pairs accordingly. Do this for all 0<= x <=2^16-1.

this turns out to be O(2^32),which is not feasible. Please suggest some alternate approach for finding count of such pairs or a different solution altogether for this problem.

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

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

You just need to do a xor convolution on the array you found :)

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

    Hmm, I dont know what xor convolution is. But thanks for the hint, I'll read about it. :)

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

      I guess he means folding with XOR. Like an array sum, but with ^ instead of +. Folding could be defined for any binary operation. For example, min_element and max_element from <algorithm> are also folds, their binary operators are min and max respectively.

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

      Suppose you have two arrays a, b. Then their XOR convolution is -

      The sum is taken over all valid i and j.

      If it was  +  operator then you could calculate this convolution with FFT. But here you can use Fast Walsh Hadamart Transform, you can learn about that here — Fast Fourier Transform and Variations of it
      However, And-convolution, Or-convolution is also possible by the way.

      → Reply