### HynDuf's blog

By HynDuf, history, 5 days ago,

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

• +28

 » 5 days ago, # |   +5 Auto comment: topic has been updated by HynDuf (previous revision, new revision, compare).
 » 4 days ago, # |   +10 What you say seems false.Consider $A=[1,3,7,8,24,63]$. In this case, the correct answer is $2$, but if you double the graph the result becomes $6/2=3$.