SortingGame
SRM 397 · 2008-04-12 · by mateuszek
SRM 397 · 2008-04-12 · by mateuszek · Graph Theory, Simple Search, Iteration, Sorting
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.
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)
{1,4,3,2,5}
5
Returns: -1
Submissions are judged against all 74 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class SortingGame with a public method int fewestMoves(vector<int> board, int k) · 74 test cases · 2 s / 256 MB per case