You are not logged in. Please login at www.codechef.com to post your questions!

×

SIMGRAPH - Editorial

0
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.

This question is marked "community wiki".

asked 12 Nov '12, 13:35

admin's gravatar image

0★admin ♦♦
19.8k350498541
accept rate: 36%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,852
×858
×10
×1

question asked: 12 Nov '12, 13:35

question was seen: 1,515 times

last updated: 12 Nov '12, 13:35