damn_me's blog

Understanding graph matching
By damn_me, 10 years ago, In English

I was trying out this problem: http://codeforces.net/contest/469/problem/D Although I thought this is a question of matching in graph. I tried doing it other way round. What I have done till now in this is: distribute elements in set A and check whether rest can be in set B or not. If not then change the above, i.e. distribute in B and then go for A. In each I will also check in the end if every element is now there in some set or not.

I know I am making mistake here and missing some test cases like the cases in which some elements can be there in either of the set and answer may be YES by distributing some elements in B which I initially kept in A. But I am unable to figure out how I should start thinking with the matching? What should be the approach for that? Not only for this question, for any other question if one could answer, that will be really helpful.

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

Comments Comments (3)
| Write comment?
»
10 years ago, # |
← Rev. 4   Vote: I like it +4 Vote: I do not like it
  • First, note that a - (a - x) = x, so the relation is bidirectional.
  • If number x is in P and number a - x is in P too, then both of them must be in the same set, which can obviously be A, but can also be B in case b - (a - x) and b - x are also in P.
  • Now, if you think of the problem as a graph problem, you can check for every number x in P whether a - x and b - x are also in P and, if so, mark them as being in the same set, which means adding an edge between them. You must also indicate whether they can belong to A, to B, or to both.
  • After constructing the graph, you must identify the components (using DSU is the easiest way) and then check if the distribution is correct (i.e. all the nodes in the component are marked as A or all are marked as B, with some of them marked as both).
→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Shouldn't it be b-(a-x) int he first point? For any point x belonging to A, and thus a-x also, the condition that it can belong to B is (b-x) and b-(a-x) must be in B.

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

      That's right, I fixed it.

      As a side note, this problem can also be solved by a Maximum Matching algorithm, but given the constraints of the problem, it wouldn't run in time.

      → Reply