Connection Status:
Competition Arena > ConversionMachine

ConversionMachine

SRM 550 · 2012-06-05 · by vexorian

SRM 550 · 2012-06-05 · by vexorian · Dynamic Programming, Math
Class Name: ConversionMachine
Return Type: int
Method Name: countAll
Arg Types: (string, string, vector<int>, int)
Problem Statement

Problem Statement

You are given two words, word1 and word2, of equal length. Their alphabet consists of only "a", "b", and "c" (quotes for clarity). You may change some characters into others for a specific cost:
  • The cost to change "a" to "b", is costs[0].
  • The cost to change "b" to "c", is costs[1].
  • The cost to change "c" to "a", is costs[2].
The remaining operations are not possible.

You are given the Strings word1 and word2, the int[] costs, and an int maxCost. Find the total number of sequences of moves that can change word1 into word2 with a total cost of at most maxCost, inclusive. Return it modulo 1000000007 (10^9+7). Two sequences of moves are different if their number of moves differ or if for some k the k-th move in one sequence changes a different position than the k-th move in the other sequence.

Notes

  • Each letter can be changed multiple times.
  • Even if a letter currently matches the corresponding letter in word2, it can still be changed.

Constraints

  • word1 and word2 will contain the same number of characters.
  • word1 and word2 will each contain between 1 and 11 characters, inclusive.
  • Each character in word1 and word2 will be 'a', 'b' or 'c'.
  • costs will contain exactly 3 elements.
  • Each element of costs will be between 1 and 1000000000 (10^9), inclusive.
  • maxCost will be between 0 and 1000000000 (10^9), inclusive.
Examples
0)
"a"
"b"
{100,2,3}
205
Returns: 2

There are two sequences of moves with a total cost of at most 205: - "a" -> "b" (Total cost = 100). - "a" -> "b" -> "c" -> "a" -> "b". (Total cost = 205).

1)
"aa"
"bb"
{102, 283, 282}
1000000
Returns: 394255315
2)
"abcba"
"abcba"
{67,23,43}
0
Returns: 1

Since the two words are equal, the empty sequence of moves is valid.

3)
"aaaaaaaaaaa"
"cbcbaaaacaa"
{1,1,1}
1000000000
Returns: 103255104
4)
"cccccccc"
"aaaaaaaa"
{10000000,1,1}
100
Returns: 40320

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

Coding Area

Language: C++17 · define a public class ConversionMachine with a public method int countAll(string word1, string word2, vector<int> costs, int maxCost) · 79 test cases · 2 s / 256 MB per case

Submitting as anonymous