TopCoder Statistics - Problem Statement

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

7000000

47

1123456789

Returns: 3661759
""

7000000

47

1987654321

Returns: 6479030
""

7000000

47

471

Returns: 5849431
"B"

1

1847635854

2147233648

Returns: 0
"B"

2

1797583853

2196388

Returns: 0
"ABB"

3

1355395163

486381

Returns: 2
"ABBA"

4

1607036031

2140324368

Returns: 2
"AAAAB"

5

1558380042

2147020398

Returns: 4
"AABAB"

6

1516333974

3298058

Returns: 4
"BBABBBB"

7

489349967

2146000780

Returns: 4
"BBABA"

8

2046595582

2084695727

Returns: 1
"ABBBAAABB"

9

758823778

45788

Returns: 5
"AABBABBAAB"

10

1585910533

1

Returns: 6
"AABABBAAAAB"

11

1007175254

2142775666

Returns: 7
"AAABABAABABB"

12

492182829

2147468613

Returns: 8
"BBAAABBABABBA"

13

1512640368

55774824

Returns: 7
"BAABBBAABABBBA"

14

2050067571

2147257689

Returns: 8
"BAAABBBBAAB"

15

1150680127

2147483284

Returns: 7
"ABBBBBAABAABBBBB"

16

1301697396

2147483637

Returns: 11
"BBBABBABBABAAAABB"

17

963875836

2147461499

Returns: 8
"AAABABBBBABAABB"

18

402545275

2147476869

Returns: 10
"ABBAABBABBABABAAABB"

19

268214787

2147482954

Returns: 10
"ABBABABABAAAAAAAAAAA"

20

1691293679

227717151

Returns: 5
"BBABABAAAABABBBBBBBBA"

21

1402024454

3

Returns: 14
"BA"

22

27067550

432

Returns: 20
"ABBAABA"

23

1792312856

2147481236

Returns: 3
"BBAABBAAAABBABAAABABBABB"

24

1781210239

1729

Returns: 14
"AABAAAAABBAABB"

25

1604168383

2147483633

Returns: 10
"ABAAAAAAABBBBAABBBAAAAAAAA"

26

546676137

2146653054

Returns: 14
"BAAAA"

27

2007325964

4926

Returns: 25
"ABBAABBAABBBABBBBAAAABABBABA"

28

763289261

2147102227

Returns: 15
"AAABBABAABABBABAAAB"

29

164618037

2123745304

Returns: 11
"BBAAABBBABAABAABBABAAABBABAAAA"

30

1800803545

2147482813

Returns: 14
"ABBAAABBAABBBBA"

6912249

326077955

490

Returns: 6912242
"BBBBABAAAAAABBABBABBAABAABBBBABBBBABABBBBBAAABABAABABABBBABBAAABB"

6075671

803987253

2147483508

Returns: 5622913
"AABBAAABBABBBBBAABAAAABABABABABBAAAAAAABABAABBABABAAAABBB"

6410758

112917720

705

Returns: 6410732
"BBABABABAAAAABBBBABAAB"

5903397

1314441501

2147483444

Returns: 13
"BBBBABAABBABBABBABBBBA"

5375659

1623874294

10494

Returns: 5375616
"AAABABBBABAAAABBABBBBAABBAABABBABAABABBABBABAAAABABBAAA"

6540593

890467798

2147483636

Returns: 29
"BABBBAABBAAABAAAABABAABBABABAABBABABAB"

5803744

830502508

5632

Returns: 5803718
"ABBBBBAAAABBBBBABBABABBBAAAABBABBAAAAABAAABBAAABBBABBABBBBABAAA"

5502432

421874798

2147483644

Returns: 33
"ABAAABBBABABABBAAAABAABABBBBAABBAAAAABAAAABBBBAABBABBBAABBBABABAABAAAABABABAAABABBAB"

5432079

1590457026

336661834

Returns: 4580826
"BABAABAAAAAAAAABAABAAABAABAAABABAAABABABBAABAAABBBBA"

5898103

1578742758

12610551

Returns: 5863389
"AAABABBBAABBAABABBAABBBABBBABABBAABAAAABABBAAABBABBBBAABABBBBABABBBAAAAABBBAAABAABBABAAAAAABBBABAABB"

6091081

1759666786

2147025113

Returns: 6087399
"ABBBAABABABBAAABAAABAABBABABAAABABAA"

5512478

1688072213

2997

Returns: 5512450
"BBBBBBAAAABBAAAAAAAABAAAA"

5523978

1475271704

2134851497

Returns: 5491228
"ABBAABAAABABBAABABABBBABABAABBAABAABABABAABBABABAAAABABAAABBBBBBBAABBBBBAABBABBABAAABBABABAABAA"

5869046

1695650247

2142948831

Returns: 5856122
"BBBAAAAABBBAABBBBBABAABBABBBBABBBBBAABBBABBABBAAAAABBBAABABAABAABAAAB"

6164614

151396815

505071775

Returns: 4715511
"ABAAAAAAAAABBBAAAABABBBBABABABBAABAAAAABAAAABBAAABBBBBBABBBBABBBBAAAABBBBBAAABABBBBBAAAAAABB"

6616493

1304793850

2147483590

Returns: 58
"AABAAABABAAAAAABBAAABBAABABBBAAABBBAAAABBBABBAAAA"

6232402

2046038195

2093151009

Returns: 6073847
"BBABABAABBAABAAAABBBBABBAAAAAAAAAAABBAABBAAABABAABBAABBAABBBBABB"

5970309

2075052142

2147091451

Returns: 5958293
"BBBBBBAAABAABABBABABABAAAABABBABBABABBBABBABAABBABBBBAAABB"

6925367

386610351

2147299922

Returns: 6922293
"AABBBBBBBAAABBBBBBBABAABBBABBBABABAABAABBBBBBABBAABABBBABAABABBBBABAB"

6067653

2064249094

2147482116

Returns: 5898796
"BBABAAABAABBBABABBBBABBBBABBBAABAABABBAAAABABBAABBBAABBAABAABBBABBABBB"

5585945

732323548

2147483646

Returns: 41
"BBAAABAABBBABBBBAAAABAA"

5151348

1796192107

2125004421

Returns: 5097651
"BBBBABABAABAAAAABABBBBBABBBABABBBAABAAABABBABBBABBAAABABAB"

5607503

1248574835

2147397927

Returns: 5604420
"BBAAABAABAABAAABBBBAAAAAAABAAAABBBBBBAABBBABABAABAAAAAABABBBAABBAABBAAABBABBBBABABBABABB"

6960825

1931908749

54398

Returns: 6960624
"AAABBBAAABBBAABBABAAABAABAAAAABBABBABBBAAABB"

6424631

302019225

3

Returns: 6424614
"ABABBB"

5258641

904693122

27342

Returns: 5258582
"AAAAABBABBBABBBBABBABABAAAAABBAAABAABBBBBBBB"

5357461

1089999389

2147128224

Returns: 5356206
"ABABABAAABAAAAABABABBABBBAAAAABBBBBABABAAABBBBBBBBABAABBBBBBBABABABAA"

5486452

1654387811

2147228962

Returns: 5472600
"BBBBABBBABABABABBBAABAABBBABABAAABBBABABBABABBABBBBBABBBABAABABBBAAAB"

6054375

589686326

472525

Returns: 6053022
"BABAABABBABBABBAAAAAAAABAAABAABABBAABAABBBAAABAABAABAB"

5803462

1900850002

2147483394

Returns: 32
"BBAABBAAAABBAAAABBABABABAABABBBBABAAABBAAABBABBABAABBAAABAABBAABBBBABB"

6580238

741745324

2146865422

Returns: 6575156
"BABBBBBBABABAABBBBBAABA"

5565493

1248462140

61776714

Returns: 5405393
"BAAAAAABABAAABA"

6016538

2057909502

48

Returns: 6016533
"AAAABABAAAABAAABBAABBAA"

5082833

1952484420

2147480744

Returns: 4906228
"AABABABBAABBAABAABBABABAAB"

6145504

1816392216

348304

Returns: 6144461
"BABAA"

5403400

217274729

2147483632

Returns: 1
"BAABABABBABBAAB"

6855444

915701050

15207

Returns: 6855396
"AABABBABABAABBABAAAAABBAABBBABBABABAABAABABBBABBABABAABABBBABBAABBAAAABABBBB"

5799899

1179698765

2147483257

Returns: 2244014
"BABBABBAABAB"

6924594

1662781606

382020800

Returns: 5691694
"BAAABAAAAAAAAABBBBABBBBABBBABBBBBBBABBBABBABBAABBAAABBBAAAAAABAAAABAABABBAAABAABBBAA"

6264039

598364207

245803

Returns: 6263237
"BAAAABAABABBAABABBAABAABABBBAABBABAAABBBBBABBAABBABBBAABBBBBABABBBBAAAABBAABBBB"

5573249

795952589

2147483643

Returns: 48
"BAABAABBBAAAAAAABAABAABBBBBBBBBAAABAABAAAAABBBBABABBBABBBAABABABA"

6430155

298062256

2147483646

Returns: 39
"BAAABBABAAABAABABBAAABAABBAABABBAAABBAABAABABABBAABBAAABBBBABABBBBAAAAAABAABBABAABABBBBB"

6198758

616629097

128665718

Returns: 5827622
"AABBABBBBBAAAAABABABABBBABBABBBBBBABABBBABAAAABBAABABAABABABBBAAAABAAB"

6827548

542765220

226398

Returns: 6826749
"AABABABABBBABBBABABABBBAAAB"

5841104

1770758136

216059556

Returns: 5253252
"BBAABABAAABBAAAAAAABABBAAAAABABBBBBABABABBBBBABABABBBBAAABABAABBABABBAAABBBAABA"

5378029

81932240

105906

Returns: 5377735
"ABB"

6589056

1570009844

2146169071

Returns: 6584409
"ABABBA"

6696991

724530287

198848

Returns: 6696346
"BABBABAABAABBBBAAAAAABABBBBABBBAABAAABBABBBBBBBBBAABBBABBABBBBABABAAAAABAAAAAABAA"

5310493

961791610

2147387337

Returns: 5301277
"ABBABAAAABBBAABBAABBABBAABABBABBABABABBBABABAAAAABABABBBBBAABBABAAAABBABABBBABAAABAABAAABBAABBAA"

5136044

2000846115

2146110787

Returns: 5131721
"BBBAB"

5

0

0

Returns: 1
"ABAAA"

5

4

4

Returns: 1
"BBBB"

4

0

0

Returns: 0
"AABAA"

6000000

47474747

1000000000

Returns: 3205457
"BBAA"

4

0

0

Returns: 0
"AABAA"

7000000

47474747

1000000000

Returns: 3739188
"BBBB"

4

123

123

Returns: 0
"BBBBBAAAAA"

10

123123123

321321321

Returns: 0
"BBBBBBBBBB"

10

0

0

Returns: 0
"BBBAAA"

6

1

1

Returns: 0
"BBAA"

4

1010

1010

Returns: 0
"BBBBBBAB"

8

123

123

Returns: 1
""

7000000

4

7

Returns: 0
"BBBAB"

5

1

1

Returns: 1
"B"

1

0

0

Returns: 0
"BBBBBBBBBBAB"

12

12

100000

Returns: 1
"BABBBBAABBABABBAAAAABABBAAABBBBAAABBBABABBBBABAABABABAABAAABBBABABABBBABABABAABABAAAAABBABAAAABAAAABBAAABBBABAAABAABBBABABBBBBBBBBBABBABABBAABABBBAAABABABABABBBBAAABABAAAAABABBBBBAABBABBABABBBBBAABBABAABBBAAAAAAABBBAABABABABAABBAABAAABBBAABAABBAAAABABBBAABAAAAABAAAAABAAAAABBAABBBBABAABBBBABBBAABAAAAAAAAABBABABAAABBAAABABBABBBBBABBABBABAAAAAABABAAAAAABBABAAABAAAABBBAABAABBBAABAABABBBBABBAABAAAAABAAABAAAAAABABBBAAABAABAAABBABBBBBAABAABABBAAABAAABAAAAABBBBAABABBABBBABABBABBABBBBBAABBBBAABBABAAABBAABAABBBBBABABBAAAABAABAAAAAAAAAABAABABABBBBAAABAAABABBABBABBAAAAAABAABBBBBABBBABBBBBABABBABAABAABBBBAABBBBBAABBBAAAABBBBBABBBBBBAAAABBAAABBAAAAABAAABBBAAABBBBABBBAAAABBBABBABBBABABABAAABABAABABBAABBBABABAAABABBBBBBABBAABABBAAAABBBBBBABBAABBABBBABABBABBAABAABAAABBAAABAABAAABBAABABABAABAAABAAAABAABBABAAAABBBBBBABABBBBBBAABAAAAABAABABBBAAAABBAABBBAABABBBBBAABBABAAABBBABBBABABBBABAAABBAABABBABBABBAABBBAABABAABBABAABAAAAABABBAAAABBAABABABBABBAABABBBABBBBAABAAABBAABABBBBBAABBBAAABABAAAAABABBAABABBBABAB"

7000000

2443

1000000000

Returns: 3739428
"BB"

2

0

0

Returns: 0
"BBB"

3

0

0

Returns: 0
"AABBBABB"

8

1

1

Returns: 6
"B"

7000000

0

0

Returns: 0
"BAA"

1281

16827

4893846

Returns: 1275
""

1000

520343481

2147483646

Returns: 0
"BBBAAA"

6

0

1

Returns: 0
"BBBBB"

5

0

0

Returns: 0
"ABAABBABAA"

10

1

1

Returns: 5
"AAAAABBAAAAAAAB"

15

0

0

Returns: 12
"B"

10

0

0

Returns: 0
"BBBB"

4

1

1

Returns: 0
"BBBBBBBAABAAABABAB"

7000000

100

987654321

Returns: 3778985

Statistics

Problem Statement for "ABBAReplace"

Problem Statement

Definition

Notes

Constraints

Examples