HynDuf's blog

By HynDuf, history, 3 years ago, In English

Recently, I came across this problem: ADABLOOM. In short, Given an array $$$A$$$ of length $$$n$$$, the problem requires us to find the number of maximum matching in which each matching $$$(i,j)$$$ satisfies $$$A_i < (A_i \oplus A_j) < A_j$$$ (XOR operator).

I found a solution here. They simply doubled the graph to make the left and right side and then find the maximum matching in the bipartite graph, and divide by $$$2$$$ to get the answer.

I know that this algorithm won't work with general graph so I want to ask the proof of correctness of this algorithm and what properties that make this kind-of-general-matching problem solvable using this method. Thanks <3

Full text and comments »

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