TopCoder problem "SortMachine" used in SRM 306 (Division II Level One)



Problem Statement

    

We have a sorting machine that works on a list of distinct numbers. This machine only has one instruction named MOVE that takes one element of the list as a parameter. The MOVE instruction removes the element from the list and then appends it to the end of the remaining list.

For example, the sequence {19,7,8,25} can be sorted in ascending order using 2 instructions:

MOVE 19, to get {7,8,25,19}

MOVE 25, to get {7,8,19,25}

You will be given a int[] a containing a list of distinct numbers. Return the minimum number of instructions required to sort the list in ascending order.

 

Definition

    
Class:SortMachine
Method:countMoves
Parameters:int[]
Returns:int
Method signature:int countMoves(int[] a)
(be sure your method is public)
    
 

Constraints

-a will have between 1 and 50 elements, inclusive.
-Each element of a will be between -1000 and 1000, inclusive.
-All elements of a will be distinct.
 

Examples

0)
    
{19,7,8,25}
Returns: 2
The example from the problem statement.
1)
    
{1,2,3,4,5}
Returns: 0
This list is already sorted, so no instructions are needed.
2)
    
{1000,-1000,0}
Returns: 1
This list can be sorted with a single instruction: MOVE 1000.
3)
    
{1,3,4,5,6,7,8,9,2}
Returns: 7
4)
    
{-2, -8, 9, 0}
Returns: 3
5)
    
{976, -946, -824, 680, -644, -95, 128, -892, 816, -263,
 -592, -669, 887, 447, -653, -759, 572, 171, 635, 98,
 -904, 78, 143, -416, -40, -846, 784, -702, -738, -858,
 582, 603, -535, 529, 84, -964, 934, 36, 783} 
Returns: 38

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=9986&pm=6413

Writer:

soul-net

Testers:

PabloGilberto , brett1479 , Olexiy , lovro , Andrew_Lazarev

Problem categories:

Greedy, Sorting