Connection Status:
Competition Arena > StringReduction

StringReduction

SRM 842 · 2022-12-01 · by misof

SRM 842 · 2022-12-01 · by misof · Dynamic Programming, Greedy
Class Name: StringReduction
Return Type: int
Method Name: reduce
Arg Types: (string, vector<int>, string)
Problem Statement

Problem Statement

You have a string of lowercase English letters: the String start.

You are also given the int[] X and the String Y. These describe some operations you can do with your string. More precisely, for each valid index i the integer X[i] and the character Y[i] describe one such operation, as specified below.


You can modify your string by performing the following operations arbitrarily many times, in any order:

  • Swap any two consecutive characters of your string.
  • For any valid index i: Select one specific group of X[i] consecutive copies of the letter Y[i]. Erase X[i]-1 of them and keep the remaining one.

Of course, an erasing rule can only be applied if the required group of identical letters exists somewhere in the current string.


For example, suppose your starting string is "abba" and we have X = {2} and Y="a". This means that whenever you encounter two consecutive 'a's, you may erase one and keep the other.

You can now modify your string as follows: start with "abba", swap the first two characters to get "baba", swap the last two characters to get "baab", and then erase one of the two consecutive 'a's we now see in the middle to get "bab".

The string "bab" can then be modified some more: we can turn it into "abb" or "bba".


Determine and return the length of the shortest string you can obtain by starting from the given string and performing a sequence of zero or more allowed operations.

Constraints

  • start will have between 1 and 2,500 characters, inclusive.
  • Each character of start will be a lowercase English letter ('a'-'z').
  • X will have between 0 and 50 elements, inclusive.
  • Each element of X will be between 1 and 2,500, inclusive.
  • The number of characters in Y will be the same as the number of elements in X.
  • Each character of Y will be a lowercase English letter ('a'-'z').
Examples
0)
"abba"
{2}
"a"
Returns: 3

The example from the statement.

1)
"abba"
{2, 3, 4, 5, 6}
"ccdef"
Returns: 4

We can rearrange the letters but no erasing rule will ever apply.

2)
"abcde"
{1}
"c"
Returns: 5

We are allowed to select one specific group of 1 consecutive copies of the letter 'c', erase 0 of them and keep the remaining one. Clearly, this operation does nothing so it makes no sense to use it.

3)
"aaaaa"
{1, 2, 3, 4, 5}
"aaaaa"
Returns: 1

One optimal solution is to use the last available erasing rule once: select all five 'a's, erase four and keep one.

4)
"aaaaaaaaaaaaa"
{12, 4, 12}
"aaa"
Returns: 1

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

Coding Area

Language: C++17 · define a public class StringReduction with a public method int reduce(string start, vector<int> X, string Y) · 83 test cases · 2 s / 256 MB per case

Submitting as anonymous