HynDuf's blog

[Help] SPOJ ADABLOOM — General Maximum Matching using Vertex Split?
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

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

»
3 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Auto comment: topic has been updated by HynDuf (previous revision, new revision, compare).

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

Sorry for spamming but please help me :<

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

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$$$.

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

    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

    → Reply