Connection Status:
Competition Arena > NextOrPrev

NextOrPrev

SRM 572 · 2012-12-13 · by lyrically

SRM 572 · 2012-12-13 · by lyrically · Greedy, Simple Search, Iteration
Class Name: NextOrPrev
Return Type: int
Method Name: getMinimum
Arg Types: (int, int, string, string)
Problem Statement

Problem Statement

Consider a string consisting of lowercase characters and following two operations that can change it:
  • Next: Choose a lowercase character other than 'z' and replace its every occurrence with the next character ('a' -> 'b', 'b' -> 'c', ..., 'x' -> 'y', 'y' -> 'z').
  • Prev: Choose a lowercase character other than 'a' and replace its every occurrence with the previous character ('b' -> 'a', 'c' -> 'b', ..., 'y' -> 'x', 'z' -> 'y').
You can use each operation as many times as you want, and in any order you like. You are given ints nextCost and prevCost. These represent the cost of using each Next and Prev operation, respectively. You are also given two Strings start and goal. These strings are special: no two characters in start are the same, and no two characters in goal are the same. Return the minimum cost required in order to transform start into goal using the above operations. If transforming start into goal is impossible, return -1 instead.

Constraints

  • nextCost and prevCost will each be between 1 and 1000, inclusive.
  • start and goal will each contain between 1 and 26 characters, inclusive.
  • start and goal will contain the same number of characters.
  • Each character in start and goal will be a lowercase character.
  • The characters in start will be distinct.
  • The characters in goal will be distinct.
Examples
0)
5
8
"ae"
"bc"
Returns: 21

There are several optimal sequences of operations. Here is one of them: "ae" -(Next)-> "be" -(Prev)-> "bd" -(Prev)-> "bc". The total cost is 5 + 8 + 8 = 21.

1)
5
8
"ae"
"cb"
Returns: -1

It is impossible to transform "ae" into "cb".

2)
1
1
"srm"
"srm"
Returns: 0

start and goal may be the same. The cost of an empty sequence of operations is 0.

3)
10
1
"acb"
"bdc"
Returns: 30
4)
10
1
"zyxw"
"vuts"
Returns: 16

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

Coding Area

Language: C++17 · define a public class NextOrPrev with a public method int getMinimum(int nextCost, int prevCost, string start, string goal) · 94 test cases · 2 s / 256 MB per case

Submitting as anonymous