BearPairs | Topcoder Archive

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.

Definition

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

Constraints

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.

Examples

```
"aabcde"
```
```
{1, 1, 100000, 100000, 100000, 100000}
```
```
2
```
```
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.

"cdbcadc"

{261,208,150,250,92,226,176}

Returns: 1402

"deebaffafdaaceaa"

{160,268,253,210,34,28,180,70,5,42,177,234,108,117,215,1}

Returns: 2507

"babbbabbbbababababbb"

{184,189,202,170,296,71,136,48,51,161,221,24,221,186,223,228,73,274,279,22}

Returns: -1

"aaaaaaaaaaaaaaaaaa"

{237,185,24,175,107,251,299,81,282,20,150,164,240,225,166,261,164,123}

Returns: -1

"acadeffbffbfccbe"

{62,113,189,161,211,150,69,60,99,212,37,274,110,265,199,192}

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)2024, Topcoder, Inc. All rights reserved.