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?
why the downvotes, may I ask?
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.
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?
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.
"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.
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.
You have to match nodes from the left to nodes from the right.