TopCoder problem "BifidSortMachine" used in SRM 306 (Division I Level One , Division II Level Two)



Problem Statement

    

We have a sorting machine that works on a list of distinct numbers. This machine only has two instructions, named MOVEBACK and MOVEFRONT. Each instruction takes one element of the list as a parameter and removes that element from the list. MOVEBACK will then append that element to the end of the remaining list, while MOVEFRONT will insert it at the beginning.

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

MOVEFRONT 7, to get {7,8,12,25,15,19}

MOVEBACK 25, to get {7,8,12,15,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:BifidSortMachine
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)
    
{8,12,25,7,15,19}
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: MOVEBACK 1000.
3)
    
{1, -10, -1, -8, 4}
Returns: 3

Problem url:

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

Problem stats url:

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

Writer:

soul-net

Testers:

PabloGilberto , brett1479 , Olexiy , lovro , Andrew_Lazarev

Problem categories:

Greedy, Simple Search, Iteration, Sorting