RearrangeFurniture
SRM 220 · 2004-11-23 · by Kawigi
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
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.
{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)
{3, 6, 2, 4, 10, 3}
{0, 1, 2, 3, 4, 5}
Returns: 0
Look at that - no work to be done!
{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.
{10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000,
10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000,
10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000,
10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000,
10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000}
{1, 2, 3, 4, 5, 6, 7, 8, 9, 10,
11, 12, 13, 14, 15, 16, 17, 18, 19, 20,
21, 22, 23, 24, 25, 26, 27, 28, 29, 30,
31, 32, 33, 34, 35, 36, 37, 38, 39, 40,
41, 42, 43, 44, 45, 46, 47, 48, 49, 0}
Returns: 980000
{5246, 3023, 9853, 5854, 3541, 7131, 8763, 9467, 6738, 196,
4787, 9945, 9931, 5695, 9862, 7717, 6321, 7399, 443, 9038,
8137, 2459, 4276, 9866, 2494, 2930, 7318, 8967, 3970, 5458,
9625, 3325, 6464, 2817, 9363, 3660, 9181, 8988, 901, 1668,
5488, 1557, 6386, 3438, 8821, 1360, 154, 5445, 6805, 9495}
{22, 40, 16, 30, 27, 5, 42, 18, 14, 37,
41, 48, 39, 43, 34, 21, 35, 11, 29, 20,
7, 49, 9, 32, 2, 0, 44, 1, 45, 15,
12, 26, 33, 23, 28, 10, 25, 38, 31, 36,
24, 4, 6, 19, 46, 47, 17, 13, 8, 3}
Returns: 295631
Submissions are judged against all 45 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class RearrangeFurniture with a public method int lowestEffort(vector<int> weights, vector<int> finalPositions) · 45 test cases · 2 s / 256 MB per case