PROBLEM LINKSDIFFICULTYCHALLENGE EXPLANATIONThis problem is a variation of the Graph Isomorphism problem. Although no efficient algorithm is known for the Graph Isomorphism problem, it is fairly easy to solve for randomly generated graphs. In this problem, you're rarely given isomorphic graphs, but instead one of the graphs is corrupted slightly (or in the extreme case, is a brand new randomly generated graph). The simplest way to get accepted on this problem is for each test case to simply output the numbers 1 through N twice. The tester's slightly better solution is to try many random permutations of 1 through N, and pick the one that gives the best answer. The setter's solution is to start with an arbitrary labelling, then repeatedly try swapping the labels of 2 vertices and see if that improves the score. Many of the best solutions use a similar strategy, but utilize bitwise operators to calculate scores faster, and occasionally start over from scratch with a new random labelling. SETTER'S SOLUTIONCan be found here. TESTER'S SOLUTIONCan be found here.
This question is marked "community wiki".
asked 12 Nov '12, 13:35
