10292. Moortal Cowmbat

Bessie has been playing the popular game Moortal Cowmbat for a long time. However, the game developers have recently released an update that forces her to change her usual play style.

The game uses m buttons, labeled with the first m lowercase letters of the Latin alphabet. Bessie’s favorite combination of moves is a string s of length n, describing a sequence of button presses. After the update, each combo must consist of a sequence of “stripes”, where a stripe is defined as a consecutive sequence of the same button pressed at least k times in a row. Bessie wants to modify her favorite combination to obtain a new string of the same length n but consisting of stripes that satisfy the updated rules.

It is known that Bessie needs a_ij days to learn to press button j instead of button i in any specific position of her combination (that is, replacing one occurrence of letter i in s with letter j costs a_ij days).

Note that sometimes the replacement can be done faster through intermediate buttons. For example, changing i directly to j may be more expensive than performing two consecutive replacements i → k → j. Thus, there may exist a transformation path from i to j with a smaller total cost than the direct replacement.

Help Bessie determine the minimum number of days required to create a combination that satisfies the new requirements.

Input. The first line contains three integers: n (1 ≤ n ≤ 10⁵), m (1 ≤ m ≤ 26) and k (1 ≤ k ≤ n).

The second line contains the string s.

The next m lines each contain m integers – the elements of the matrix a_ij, where a_ij is the number of days required to replace button i with button j. It is guaranteed that 0 ≤ a_ij ≤ 1000 and a_ii = 0 for all i.

Output. Print the minimum number of days Bessie needs to create a combination that meets the new requirements.

Sample input	Sample output
5 5 2 abcde 0 1 4 4 4 2 0 4 4 4 6 5 0 3 2 5 5 5 0 4 3 7 0 5 0	5

SOLUTION

dynamic programming

Algorithm analysis

Let’s run the Floyd – Warshall algorithm on the matrix a_ij to determine the shortest time required to replace each letter with any other letter.

Then construct a cost matrix cst, where cst[i][j] (1 ≤ i ≤ n) represents the minimum number of days needed to change the letter s[i – 1] into the letter j.

For convenience in further calculations, we build a matrix ps that contains the column-wise prefix sums of the cost matrix cst:

ps[i][j] = cst[i][1] + cst[i][2] + … + cst[i][j]

Let dp[i][j] denote the minimum number of days required to transform the first i letters of the string s into a string that satisfies Bessie’s new requirements, with the last k letters of the new string being the letter j.

We can write the dynamic equations as follows:

· Suppose the first i – 1 letters of s have already been transformed into a string whose last k letters are all j. Then we simply change the letter s[i – 1] to j, which can be done in cst[i][j] days.

dp[i][j] = dp[i – 1][j] + cst[i][j]

· To ensure that the last k letters of the new string are all j, consider the values dp[i – k][0], dp[i – k][1], …, dp[i – k][m – 1]. Choose the smallest among them – that is, we transform the first i – k letters of s into a string satisfying Bessie’s new requirements (we don’t care which letter the substring of length i – k ends with; we only care that it can be obtained in the minimum number of days). After that, we replace the last k letters of the original string s – namely s[i – k], s[i – k + 1], …, , s[i – 1] – with the letter j, which takes

cst[i – k + 1][j] + cst[i – k + 2][j] + … + cst[i][j]

days. This sum can be computed in constant time using the prefix sum array ps:

cst[i – k + 1][j] + cst[i – k + 2][j] + … + cst[i][j] = ps[i][j] – ps[i – k][j]

We maintain an auxiliary array mn, where

mn[i] = min(dp[i][0], dp[i][1], …, dp[i][m – 1])

Thus, the dynamic programming equation for this case (i ≥ k) takes the following form:

dp[i][j] = ps[i][j] – ps[i – k][j] + mn[i – k]

It remains to choose the smaller of the two options for dp[i][j].

The answer to the problem is the value

mn[n] = min(dp[n][0], dp[n][1], …, dp[n][m – 1])

We don’t care which particular k letters the new word Bessie ends with.

Example

In this example, the optimal solution is as follows: replace a with b, then d with e, and after that replace both e’s with c. The total cost of the changes is 1 + 4 + 0 + 0 = 5 days, and the resulting string will be bbccc.

Using the matrix a_ij, we construct the cost matrix cst. We also compute the matrix ps.

All values of dp[1][j] (0 ≤ j ≤ 4) will be equal to +∞, since the length of the stripe cannot be less than k = 2. Accordingly, mn[1] = +∞.

Let us now consider the process of computing the values of dp[2][j] (0 ≤ j ≤ 4).

· dp[2][0] = (“ab” → “aa”) = cnt[‘a’][‘a’] + cnt[‘b’][‘a’] = 0 + 2 = 2;

· dp[2][1] = (“ab” → “bb”) = cnt[‘a’][‘b’] + cnt[‘b’][‘b’] = 1 + 0 = 1;

· dp[2][2] = (“ab” → “cc”) = cnt[‘a’][‘c’] + cnt[‘b’][‘c’] = 4 + 4 = 8;

· dp[2][3] = (“ab” → “dd”) = cnt[‘a’][‘d’] + cnt[‘b’][‘d’] = 4 + 4 = 8;

· dp[2][4] = (“ab” → “ee”) = cnt[‘a’][‘e’] + cnt[‘b’][‘e’] = 4 + 4 = 8;

mn[2] = min(dp[2][0], dp[2][1], dp[2][2], dp[2][3] , dp[2][4]) = 1

When computing the values of dp[3][j] (0 ≤ j ≤ 4), the equation

dp[3][j] = ps[3][j] – ps[1][j] + mn[1]

will not be used, since mn[1] = +∞. Therefore, to obtain strips from the first three letters, one can only extend the strips of length two that have already been constructed:

· dp[3][0] = dp[2][0] + cst[‘c’][‘a’] = 2 + 5 = 7 (“aaa”);

· dp[3][1] = dp[2][1] + cst[‘c’][‘b’] = 1 + 5 = 6 (“bbb”);

· dp[3][2] = dp[2][2] + cst[‘c’][‘c’] = 8 + 0 = 8 (“ccc”);

· dp[3][3] = dp[2][3] + cst[‘c’][‘d’] = 8 + 3 = 11 (“ddd”);

· dp[3][4] = dp[2][4] + cst[‘c’][‘e’] = 8 + 2 = 10 (“eee”);

The value of dp[4][0] can be obtained in two ways:

· dp[4][0] = dp[3][0] + cst[‘d’][‘a’] = 7 + 5 = 12 (“aaaa”);

or

· dp[4][0] = ps[4][0] – ps[2][0] + mn[2] = 12 – 2 + 1 = 11 (“bbaa”)

The second case is more optimal – two letters ‘a’ are appended to a two-character string. The value mn[2] = 1 is achieved for the string “bb”, which means the optimal string is “bbaa”.

Algorithm implementation

Let us define the following arrays:

· a[i][j] – the minimum cost of transforming letter i into letter j.

· cst[i][j] – the cost of replacing the i-th letter of the original string s (indexing starts from 1) with letter j. Formally

cst[i][j] = a[s[i - 1] - 'a'][j]

· ps – the prefix sum array of cst, used to quickly compute the cost of changing a substring of length k:

ps[i][j] = cst[1][j] + cst[2][j] + ... + cst[i][j]

· dp[i][j] – the minimum number of days required to transform the first i letters of string s into a valid string (according to the stripe rules), where the last k letters of the result are letter j.

· mn[i] – the minimum over all j of dp[i][j], i.e. the best solution for the first i characters.

#define MAXN 100005

#define ALPH 26

int a[ALPH][ALPH], cst[MAXN][ALPH], ps[MAXN][ALPH], dp[MAXN][ALPH],

mn[MAXN];

Read the input data.

cin >> n >> m >> k;

cin >> s;

for (i = 0; i < m; i++)

for (j = 0; j < m; j++)

cin >> a[i][j];

Run the Floyd – Warshall algorithm on the matrix a. After it finishes, a[i][j] contains the minimum number of days required to change letter i into letter j.

for (x = 0; x < m; x++)

for (i = 0; i < m; i++)

for (j = 0; j < m; j++)

a[i][j] = min(a[i][j], a[i][x] + a[x][j]);

We have m ≤ 26 letters. Let us construct a cost matrix cst such that cst[i][j] (1 ≤ i ≤ n) contains the minimum number of days required to change the letter s[i – 1] into letter j. The letters in the string s are indexed starting from 0.

For convenience in further computations, we’ll build a matrix ps, which contains the column-wise prefix sums of the cost matrix cst:

ps[i][j] = cst[i][1] + cst[i][2] + … + cst[i][j]

for (i = 1; i <= n; i++)

for (j = 0; j < m; j++)

{

cst[i][j] = a[s[i - 1] - 'a'][j];

ps[i][j] = ps[i - 1][j] + cst[i][j];

}

Initialize the arrays.

memset(dp, 0x3f, sizeof dp);

memset(mn, 0x3f, sizeof mn);

mn[0] = 0;

We compute the values of the dp array cells. The letter i corresponds to the character s[i – 1]. The letters in variable j are numbered from 0 (corresponding to letter ‘a’) to m – 1. Intuitively, at each step i, Bessie decides:

· either to continue pressing the same button as before,

· or to start a new stripe of length at least k.

We choose the cheaper option and save the result in dp[i][j].

for (i = 1; i <= n; i++)

for (j = 0; j < m; j++)

{

We continue the current stripe. The letter s[i – 1] of the original string is changed to j. That is:

· the previous i – 1 letters have already been transformed and end with j;

· now add the i-th letter s[i – 1], also turning it into j;

· the total cost will be dp[i – 1][j] + cst[i][j].

dp[i][j] = min(dp[i][j], dp[i - 1][j] + cst[i][j]);

We start a new stripe of k letters. We assume that at position i a new stripe of exactly k (or more) letters ends, consisting of the letter j. To do this:

· Take the best transformation of the first (i – k) letters (everything before the new stripe): mn[i – k].

· Add the cost of replacing the last k letters (from i – k + 1 to i) with j:

ps[i][j] - ps[i - k][j]

If fewer than k characters have been processed, a stripe of this length cannot be formed. Therefore, i ≥ k.

if (i >= k)

dp[i][j] = min(dp[i][j], ps[i][j] - ps[i - k][j] + mn[i - k]);

After computing all dp[i][j] for a fixed i, we store the best (minimum) value among all j in mn[i].

mn[i] = min(mn[i], dp[i][j]);

}

Print the answer.

cout << mn[n] << "\n";