SPIN - Editorial

challenge
dec11
editorial
spin

#1

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 :slight_smile:

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.