TopCoder Statistics - Problem Statement

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

{1,2,3}

3

Returns: 0

The sequence is already sorted, so we don't need any moves.
{3,2,1}

3

Returns: 1

We can reverse the whole sequence with one move here.
{5,4,3,2,1}

2

Returns: 10

This one is more complex.
{3,2,4,1,5}

4

Returns: -1
{1,4,3,2,5}

5

Returns: -1
{2,5,1,4,3}

3

Returns: -1
{2,5,3,4,1}

3

Returns: -1
{4,3,1,5,2}

2

Returns: 6
{2,1,4,3,5}

3

Returns: -1
{5,4,1,2,3}

3

Returns: 3
{5,2,1,4,3}

3

Returns: 2
{5,4,3,2,1}

3

Returns: 4
{2,4,6,5,3,1}

2

Returns: 9
{6,3,1,2,5,4}

2

Returns: 8
{3,4,6,2,5,1}

4

Returns: -1
{4,1,2,3,5,6}

3

Returns: -1
{3,4,2,6,5,1}

2

Returns: 8
{2,5,6,3,1,4}

4

Returns: 6
{5,6,3,2,1,4}

3

Returns: 5
{2,6,4,3,7,5,1}

3

Returns: -1
{2,4,6,7,1,5,3}

4

Returns: 7
{1,2,3,4,5,6,7}

2

Returns: 0
{5,4,2,1,6,3,7}

2

Returns: 9
{2,1,5,4,3,7,6}

2

Returns: 5
{1,4,6,7,2,5,3}

4

Returns: -1
{2,6,4,1,7,3,5}

2

Returns: 9
{1,5,2,3,4,7,6}

3

Returns: -1
{1,6,3,4,2,7,5}

5

Returns: -1
{3,2,7,4,5,6,1}

5

Returns: 4
{2,3,4,5,6,7,1}

6

Returns: 6
{7,6,5,4,3,2,1}

6

Returns: 7
{7,6,5,4,3,2,1}

2

Returns: 21
{8,7,6,5,4,3,2,1}

2

Returns: 28
{8,5,1,2,4,3,6,7}

3

Returns: -1
{7,2,1,6,8,4,3,5}

4

Returns: 7
{8,1,4,6,5,7,2,3}

2

Returns: 16
{6,2,5,8,3,1,7,4}

5

Returns: -1
{6,7,3,2,4,5,8,1}

3

Returns: -1
{7,8,5,6,3,4,1,2}

3

Returns: 12
{8,7,6,5,4,3,2,1}

7

Returns: -1
{5,6,7,8,1,2,3,4}

7

Returns: 4
{8,7,6,5,4,3,2,1}

8

Returns: 1
{8,7,6,5,4,3,2,1}

2

Returns: 28
{8,6,5,2,3,4,7,1}

4

Returns: 10
{7,4,1,6,3,8,5,2}

5

Returns: 7
{8,7,6,5,4,3,2,1}

6

Returns: 28
{8,7,6,5,4,3,2,1}

8

Returns: 1
{7,6,5,4,3,2,1}

3

Returns: 9
{6,1,4,2,7,5,3}

4

Returns: 9
{3,6,7,4,1,2,5}

5

Returns: 7
{5,6,3,4,1,2}

3

Returns: 6
{6,4,2,5,3,1}

4

Returns: 11
{3,2,1,6,5,4}

5

Returns: 3
{5,4,3,2,1}

4

Returns: 5
{1,2}

2

Returns: 0
{2,1}

2

Returns: 1
{1,2,3,4,5,6,8,7}

4

Returns: -1
{7, 5, 3, 4, 8, 2, 6, 1 }

2

Returns: 19
{3, 2, 1 }

3

Returns: 1
{7, 2, 1, 6, 8, 4, 3, 5 }

4

Returns: 7
{5, 4, 3, 2, 1 }

2

Returns: 10
{7, 2, 1, 6, 8, 4, 3, 5 }

2

Returns: 14
{1, 2, 3, 4, 5, 6 }

3

Returns: 0
{8, 7, 6, 5, 4, 3, 2, 1 }

2

Returns: 28
{8, 4, 7, 2, 1, 5, 3, 6 }

4

Returns: -1
{8, 7, 6, 5, 4, 3, 2, 1 }

6

Returns: 28
{4, 2, 5, 7, 1, 8, 3, 6 }

6

Returns: 21
{7, 1, 2, 8, 6, 4, 3, 5 }

6

Returns: 14
{8, 7, 6, 5, 4, 3, 2, 1 }

4

Returns: 6
{5, 3, 2, 4, 1, 7, 8, 6 }

3

Returns: -1
{7, 2, 1, 6, 8, 4, 3, 5 }

3

Returns: -1
{4, 5, 3, 8, 7, 1, 2, 6 }

4

Returns: -1
{6, 4, 1, 7, 3, 8, 5, 2 }

6

Returns: 23
{5, 3, 8, 2, 1, 4, 6, 7 }

6

Returns: 18

Statistics

Problem Statement for "SortingGame"

Problem Statement

Definition

Constraints

Examples