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

×

SPIN - Editorial

PROBLEM LINKS

Practice
Contest

DIFFICULTY

CHALLENGE

EXPLANATION

The easiest way to get accepted is to output a sequence of 100 random moves for N = 2 and -1 for all other cases. Not that it really matters :)

One of the simplest good approaches is the following. Let's fix color C into which we're going to color all the wheels. Let's say that a wheel is reachable from C if it can be colored into C through a sequence of moves each of which rotates a wheel of color C. It's easy to check this for all wheels in O(NM) total time. Let's rotate some random wheel from those which are not reachable from C several times until all of the wheels are reachable. When this finally happens, let's rotate some random wheel of color C so that at least one of the wheels is colored into C at the first iteration. It can be seen that we'll actually color all the wheels into C pretty quickly. This approach is enough to get a score of under 450.

Other solutions should probably use a similar idea. Tiancheng Lou's solution receiving a score of under 303 also makes use of beam search, as it can be inferred from his code.

SETTER'S SOLUTION

Can be found here.

TESTER'S SOLUTION

Can be found here.

This question is marked "community wiki".

asked 22 Nov '12, 17:04

admin's gravatar image

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

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,719
×847
×6
×1

question asked: 22 Nov '12, 17:04

question was seen: 970 times

last updated: 22 Nov '12, 17:04