TopCoder problem "SortingGame" used in SRM 397 (Division I Level One , Division II Level Two)



Problem Statement

    In The Sorting Game, you are given a sequence containing a permutation of the integers between 1 and n, inclusive. In one move, you can take any k consecutive elements of the sequence and reverse their order. The goal of the game is to sort the sequence in ascending order. You are given a int[] board describing the initial sequence. Return the fewest number of moves necessary to finish the game successfully, or -1 if it's impossible.
 

Definition

    
Class:SortingGame
Method:fewestMoves
Parameters:int[], int
Returns:int
Method signature:int fewestMoves(int[] board, int k)
(be sure your method is public)
    
 

Constraints

-board will contain between 2 and 8 elements, inclusive.
-Each integer between 1 and the size of board, inclusive, will appear in board exactly once.
-k will be between 2 and the size of board, inclusive.
 

Examples

0)
    
{1,2,3}
3
Returns: 0
The sequence is already sorted, so we don't need any moves.
1)
    
{3,2,1}
3
Returns: 1
We can reverse the whole sequence with one move here.
2)
    
{5,4,3,2,1}
2
Returns: 10
This one is more complex.
3)
    
{3,2,4,1,5}
4
Returns: -1
4)
    
{7,2,1,6,8,4,3,5}
4
Returns: 7

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=8745

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=12169&pm=8745

Writer:

mateuszek

Testers:

PabloGilberto , Olexiy , ivan_metelsky , ged

Problem categories:

Graph Theory, Simple Search, Iteration, Sorting