PROBLEM LINKS
DIFFICULTY
CHALLENGE
EXPLANATION
This 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 SOLUTION
Can be found here.
TESTER’S SOLUTION
Can be found here.