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
Auto comment: topic has been updated by HynDuf (previous revision, new revision, compare).
Sorry for spamming but please help me :<
Pls :<
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$$$.
Thanks so much for answering. You are so correct! The testcase of the problem was pretty weak :<. I thought that I could learn something new but it turned out to be a wrong solution.
Anyway, if you could give me some hints on how this problem can be solved, I would really appreciate. Thanks