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

×

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

19.8k350498541
accept rate: 35%

 toggle preview community wiki:
Preview

### Follow this question

By Email:

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

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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