Get Time

   Problem Statement  

 Problem Statement for BearPairs

Problem Statement


Note that this problem has an unusual time limit: 14 seconds.

Bear Limak asks you to solve the following problem.

You are given a String s of length n. Each character in s is one of the first six lowercase letters: {a,b,c,d,e,f}.

You are also given a very small int k. The parity of k is the same as the parity of n. Your task is to make exactly (n-k)/2 operations. In each operation you must swap two distinct letters. (E.g., you cannot swap an 'a' with another 'a'.) You cannot move any character more than once.

In other words, out of the n letters in s exactly k have to remain in place, the other n-k have to be divided into disjoint pairs of distinct letters, and each of those pairs has to be swapped.

Each swap has a cost. You are given a int[] cost. Swapping the characters at 0-based indices i and j costs 100*abs(i-j) + cost[i] + cost[j].

Return -1 if it's impossible to make required number of operations. Otherwise, compute and return the smallest possible total cost of making the required swaps.



Parameters:String, int[], int
Method signature:int minCost(String s, int[] cost, int k)
(be sure your method is public)


-n will be between 2 and 2500, inclusive.
-s will have exactly n characters.
-cost will have exactly n elements.
-k will be between 0 and 6, inclusive.
-k will be not greater than n.
-n and k will have the same parity.
-Each character in s will be one of the first lowercase letters: {a,b,c,d,e,f}.
-Each element in cost will be between 1 and 10^5, inclusive.


{1, 1, 100000, 100000, 100000, 100000}
Returns: 200402
One optimal solution is to make two swaps: (0,2) and (1,3). That is, we exchange s[0] with s[2] and then s[1] with s[3]. Each of these swaps costs 2*100 + 1 + 100000 = 100201 for a total cost of 200402.

Another optimal solution is to make the swaps (0,3) and (1,2). These two swaps cost 100301 and 100101, respectively, so the total cost is the same.

Note that we are not allowed to make the swap (0,1) because s[0] and s[1] are both 'a's.
Returns: 1402
Returns: 2507
Returns: -1
Returns: -1
Returns: 2235

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.

This problem was used for:
       Single Round Match 680 Round 1 - Division I, Level Three