pranet's blog

SPOJ Jolly Kingdom (Minimum Vertex Cover?)
By pranet, history, 9 years ago, In English

Problem

TL;DR version: You are given a bipartite graph with atmost 1000 vertices on each side. M (upto 1,000,000) edges are added one by one. Compute the minimum vertex cover after each addition.

Clarification: You need to compute the minimum vertex cover / maximum matching everytime an edge is added.

Any ideas?

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

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

Kőnig's theorem will definitely help

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

    Obviously. However, the problem is that I cannot compute the maximum matching naively 1e6 times....

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

      Maybe the trick is to effectively check (after adding each edge) whether there exists a new augmenting path. There will be no more than min(N, M) such paths, so we can afford running some calculations on the entire graph after finding each augmenting path. Author says, that his approach uses about 700kk operations, so this may be it.

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it +7 Vote: I do not like it

        "Maybe the trick is to effectively check (after adding each edge) whether there exists a new augmenting path"

        This is what I'm seeking help on...

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

          Ok, so just build a directed graph with one vertex representing all unmatched vertices in the first set (vertex A) and other one representing unmatched vertices in the second set (vertex B). Other vertices will correspond to pairs of matched vertices. Each unmatched edge in original graph connecting vertices a and b will translate to directed edge between a' and b', where v' is a vertex in new graph corresponding to original vertex v in the old graph. Direction of this edge will be from a' to b' if a was in the same set as A in our original graph and from b' to a' in the opposite case. The task now is to determine whether after adding new edge there exist a path from A to B.

          → Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

I know one of the guys who solved that problem, lucasmelo, and he only solved it because I kept bothering him to help me with it, though you can see I still don't have an accepted in it = ).

If I remember correctly (I can't find our talk) he checks, when a new monster arrives, if it is covered by his choice of guards in the previous iteration, if it is our answer is the same from the previous iteration. Otherwise he runs the hopcroft-karp code from wikipedia and gets a new min vertex cover. I also think he did the problem backwards (going from all monsters to zero monsters) but I can't think now how he did that

I don't know if that was the intended solution as his time is way slower than the other guy time.

→ Reply