TopCoder problem "RearrangeFurniture" used in SRM 220 (Division I Level Three)



Problem Statement

    

Kawigi's furniture is all in the wrong places in his new apartment. He needs to move all of it into the appropriate spots. The problem is that he has so much furniture and very limited room to move it in. Because of this, the only action he can take to rearrange his furniture is to swap two pieces of furniture.

He would like to exert as little physical effort as possible in doing this task, where the effort of swapping two pieces of furniture is defined as the sum of the weights of the two objects to be swapped. You need to figure out what the minimum effort required to put all of the furniture in the correct places.

You will be given two int[]s, the first is the weights of each piece of furniture (element 0 of the int[] will be the weight of furniture 0, element 1 will be the weight of furniture 1, etc). The second int[] is the location where each piece of furniture is supposed to end up (furniture 0 starts out in location 0, furniture 1 starts out in location 1, etc). You are to find and return the minimum cost required to put the furniture in their rightful locations.

 

Definition

    
Class:RearrangeFurniture
Method:lowestEffort
Parameters:int[], int[]
Returns:int
Method signature:int lowestEffort(int[] weights, int[] finalPositions)
(be sure your method is public)
    
 

Constraints

-weights and finalPositions will each have between 1 and 50 elements.
-weights and finalPositions will have the same number of elements.
-finalPositions will have the numbers 0 through n-1 inclusive, exactly once, where n is the number of elements in the array.
-The elements in weights will be between 1 and 10000.
 

Examples

0)
    
{5, 4, 7, 3, 10}
{1, 2, 0, 4, 3}
Returns: 33
One way to do this with the minimum effort is like so:

step 0: {0, 1, 2, 3, 4}

step 1: {0, 2, 1, 3, 4} (cost: 11)

step 2: {1, 2, 0, 3, 4} (cost: 9)

step 3: {1, 2, 0, 4, 3} (cost: 13)
1)
    
{3, 6, 2, 4, 10, 3}
{0, 1, 2, 3, 4, 5}
Returns: 0
Look at that - no work to be done!
2)
    
{10, 3, 123, 498, 12, 13, 14, 45, 32, 67,
 111, 234, 543, 2, 12, 1, 56, 67, 78, 89,
 12, 90, 23, 77, 345, 543, 242, 560, 121, 232,
 980, 10000, 12, 1, 6, 98, 67, 44, 21, 456,
 3231, 456, 23, 14, 678, 65, 45, 23, 99, 23}
{49, 48, 47, 46, 45, 44, 43, 42, 41, 40,
 39, 38, 37, 36, 35, 34, 33, 32, 31, 30,
 29, 28, 27, 26, 25, 24, 23, 22, 21, 20,
 19, 18, 17, 16, 15, 14, 13, 12, 11, 10,
 9, 8, 7, 6, 5, 4, 3, 2, 1, 0}
Returns: 20597
On this one, you just have to swap two elements into place 25 times.

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=5866&pm=3076

Writer:

Kawigi

Testers:

PabloGilberto , lbackstrom , brett1479

Problem categories:

Greedy, Math