ABBAReplace | Topcoder Archive

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) &lt; N:
    state = (state * 1103515245 + 12345) modulo 2^31
    if state &lt; threshold:
        S += 'A'
    else:
        S += 'B'

Given the string S, compute and return the number of rewriting steps.

Definition

Class:: ABBAReplace
Method:: countSteps
Parameters:: String, int, int, int
Returns:: int
Method signature:: int countSteps(String Sprefix, int N, int seed, int threshold)
(be sure your method is public)

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.

Examples

```
"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.

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.