Connection Status:
Competition Arena > BearPairs

BearPairs

SRM 680 · 2016-01-04 · by Errichto

SRM 680 · 2016-01-04 · by Errichto · Dynamic Programming, Search
Class Name: BearPairs
Return Type: int
Method Name: minCost
Arg Types: (string, vector<int>, int)
Problem Statement

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.

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
0)
"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.

1)
"cdbcadc"
{261,208,150,250,92,226,176}
1
Returns: 1402
2)
"deebaffafdaaceaa"
{160,268,253,210,34,28,180,70,5,42,177,234,108,117,215,1}
2
Returns: 2507
3)
"babbbabbbbababababbb"
{184,189,202,170,296,71,136,48,51,161,221,24,221,186,223,228,73,274,279,22}
4
Returns: -1
4)
"aaaaaaaaaaaaaaaaaa"
{237,185,24,175,107,251,299,81,282,20,150,164,240,225,166,261,164,123}
4
Returns: -1

Submissions are judged against all 18 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class BearPairs with a public method int minCost(string s, vector<int> cost, int k) · 18 test cases · 2 s / 256 MB per case

Submitting as anonymous