Scribd
Upload
18 views3 pages

String Rewriting Steps in Golang

The problem is to count the number of rewriting steps needed to convert a given string S to its final form using the rule that replaces every "AB" substring with "BA". The method countsSteps takes a prefix string, length N, seed and threshold to generate additional characters for S if needed, and returns the number of rewriting steps for the resulting string S. It should handle long strings and integer overflow issues.

Uploaded by

jeusl
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
18 views3 pages

String Rewriting Steps in Golang

The problem is to count the number of rewriting steps needed to convert a given string S to its final form using the rule that replaces every "AB" substring with "BA". The method countsSteps takes a prefix string, length N, seed and threshold to generate additional characters for S if needed, and returns the number of rewriting steps for the resulting string S. It should handle long strings and integer overflow issues.

Uploaded by

jeusl
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

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.

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)
Limits
Time limit (s):
 
2.000
Memory limit (MB):
 
256

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
0)
"AABABB"
6
0
0
Returns: 4
The example from the problem statement.
1)
""
0
4
7
Returns: 0
An empty string.
2)
"ABBABAABABBBABBBB"
17
0
0
Returns: 11
S = Sprefix.
3)
"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)2003, TopCoder, Inc. All rights reserved.

You might also like