pabloskimg's blog

ICPC Latin America Regional 2012 — Game of Tiles — is it really bipartite matching? how? why?
By pabloskimg, history, 6 years ago, In English

Based on some spoilers I "know" that the problem Game of Tiles from 2012 ICPC Latin America Regional Contest should be solved using maxflow / bipartite matching. However, I still haven't been able to figure out a correct solution for it based on bipartite matching. Does anybody know how to apply bipartite matching, or any algorithm for that matter, to solve the problem? If so, would you kindly share the logic behind your solution?

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

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

why the downvotes, may I ask?

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

First of all, I also don't understand the downvotes. I couldn't find the solution and it's an interesting problem so I looked for it https://github.com/jonathandrnd/ACMICPC_LatinAmericaSolution/blob/master/solucionario%20regional%202012/g.cpp

For each connected component, the second player wins if and only if there's a perfect match. This perfect match is the set of moves that the player needs to do to win. It's easy to see that if there's a perfect match the second player wins. I'm not sure how to prove the other part of the iff.

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    You are right, if there is perfect match, player 2 always wins by choosing the match for each player 1's move. But if there is NO perfect match, how do you prove player 1 always wins? What would the optimal strategy be for player 1 if there is no perfect match?

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

      If there is no perfect match, the first player can choose any cell that doesn't belong to maximum matching as the starting cell. Then the second player is forced to move into a cell that belongs to the matching, then the first player can move to the cell matched with the current cell, then the second player is again forced to move into a cell belonging to the matching (and the cell matched to that cell is still not visited), and so on — the first player can always optimally answer the second player's action in such a way that after his turn every pair in the matching is either not visited at all, or visited completely (i. e. both its cells are already filled).

      The second player cannot choose any cell that does not belong to the maximum matching, because it would imply that the path from the starting cell to this cell is an augmenting path, so the matching is not optimal.

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

        "The second player cannot choose any cell that does not belong to the maximum matching, because it would imply that the path from the starting cell to this cell is an augmenting path, so the matching is not optimal." This is the proof I was looking for, you are completely right. But I still have a question. Or meta-question to be more accurate. How can you come up with this kind of proofs quickly during a contest? Are there any "reasoning heuristics" one could apply to quickly find correctness proofs for candidate solutions for a problem? I usually only implement solutions when I feel logically convinced of their correctness, but in problems like this I just don't see myself coming up with proofs at all.

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

King from Google Code Jam 2008 is a very similar problem, so I think the analysis will be useful: https://code.google.com/codejam/contest/32008/dashboard#s=a&a=3. It requires non-bipartite matching because kings can move diagonally, but the same idea can be used in your problem with a bipartite matching algorithm.

→ Reply
»
6 years ago, # |
  Vote: I like it -7 Vote: I do not like it

You have to match nodes from the left to nodes from the right.

→ Reply