SortingGame | Topcoder Archive

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
```
```
{7,2,1,6,8,4,3,5}
```
```
4
```
```
Returns: 7
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.