Блог пользователя damn_me

Understanding graph matching
Автор damn_me, 10 лет назад, По-английски

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.

  • Проголосовать: нравится
  • +2
  • Проголосовать: не нравится

»
10 лет назад, # |
← Rev. 4   Проголосовать: нравится +4 Проголосовать: не нравится
  • 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).
→ Ответить
  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    → Ответить
    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

      → Ответить