TopCoder problem "InsertSort" used in SRM 351 (Division II Level Three)



Problem Statement

    

We have an array A and we want to sort it in non-decreasing order. The only allowable operation is to move one element of the array into any other place (before all elements, after all elements or between any two adjacent elements). The cost of the single operation is equal to the value of the moved element. We want to minimize the total cost of sorting the array.

For example, we have an array {7, 1, 2, 3}. We can sort it by moving 7 from the head to the tail. But the cost of this operation is 7 which is not optimal. The optimal sorting algorithm is to consecutively move 1, 2 and 3 to the proper places before 7. The total cost of these three movements will be 1+2+3=6, which is less than 7.

You will be given a int[] theArray. Return the minimal total cost required to sort the array.

 

Definition

    
Class:InsertSort
Method:calcMinimalCost
Parameters:int[]
Returns:int
Method signature:int calcMinimalCost(int[] theArray)
(be sure your method is public)
    
 

Constraints

-theArray will contain between 1 and 50 elements, inclusive.
-Each element of theArray will be between 1 and 1000, inclusive.
 

Examples

0)
    
{7, 1, 2, 3}
Returns: 6
The example from the problem statement.
1)
    
{7, 1, 2, 5}
Returns: 7
The cheapest way to sort the array is to move 7 from the head to the tail.
2)
    
{1, 8, 8, 12, 99}
Returns: 0
The array is already sorted.
3)
    
{8, 2, 6, 5, 1, 4}
Returns: 18
4)
    
{6, 4, 5, 3, 8, 2, 7, 2, 11, 2, 2}
Returns: 24

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10675&pm=4844

Writer:

Andrew_Lazarev

Testers:

PabloGilberto , brett1479 , Olexiy

Problem categories:

Dynamic Programming