SIMGRAPH - Editorial

april12
challenge
editorial
simgraph

#1

PROBLEM LINKS

Practice
Contest

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.