ABBAReplace
SRM 783 · 2020-03-30 · by misof
Problem Statement
Consider a very simple string rewriting system. We have a string over the alphabet {A,B}. In each step, we find all occurrences of "AB" in the current string and we change each of them into "BA".
For example, if we start with the string "AABABB", the rewriting will go as follows:
0: AABABB 1: ABABAB 2: BABABA 3: BBABAA 4: BBBAAA
At this point, the rewriting has stopped, as there are no more "AB" substrings in the current string.
Use the following pseudocode to generate a string S of length N:
state = seed
S = Sprefix
while length(S) < N:
state = (state * 1103515245 + 12345) modulo 2^31
if state < threshold:
S += 'A'
else:
S += 'B'
Given the string S, compute and return the number of rewriting steps.
Notes
- The reference solution does not depend on any properties of the pseudorandom generator.
Constraints
- Sprefix will contain between 0 and 1000 characters, inclusive.
- Each character of Sprefix will be 'A' or 'B'.
- N will be between len(Sprefix) and 7,000,000, inclusive.
- seed will be between 0 and 2^31 - 1, inclusive.
- threshold will be between 0 and 2^31 - 1, inclusive.
"AABABB" 6 0 0 Returns: 4
The example from the problem statement.
"" 0 4 7 Returns: 0
An empty string.
"ABBABAABABBBABBBB" 17 0 0 Returns: 11
S = Sprefix.
"AABAA" 17 47474747 1000000000 Returns: 10
The string you should generate is S = "AABAAABAAABBBAAAA". The sequence of values in the "state" variable during generation is as follows: 81038168 1862554801 143404438 831999255 766706948 1708690157 2010484002 1631167411 81620336 507504873 660822382 597739535 Watch out for integer overflow.
"" 7000000 47 1123456789 Returns: 3661759
Submissions are judged against all 117 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class ABBAReplace with a public method int countSteps(string Sprefix, int N, int seed, int threshold) · 117 test cases · 2 s / 256 MB per case