Statistics

Problem Statement for "DominatedSubstrings"

Problem Statement

All strings in this problem are strings of uppercase letters 'A', 'B', and 'C'.


We say that:

  • A string w is strongly dominated by x if the number of occurrences of x in w exceeds length(w)/2.
  • A string w is weakly dominated by x if the number of occurrences of x in w equals length(w)/2.

For example: "ABACA" is strongly dominated by 'A', "AABBCA" is weakly dominated by 'A', "ABBA" is weakly dominated by both 'A' and 'B', and "ABCABC" is not dominated by any letter.


We now say that:

  • A string w is prefix-dominated by x if each of its prefixes (including w itself) is either strongly or weakly dominated by x.
  • A string w is prefix-dominated if it's prefix-dominated for any x.

For example, "ABAB" and "AABA" are both prefix-dominated by 'A' (and therefore prefix-dominated) while "BAAB" is not prefix-dominated by any letter. This is because 'A' does not dominate the prefix "B" (neither strongly nor weakly), 'B' does not dominate the prefix "BAA", and 'C' does not dominate any of the non-empty prefixes of "BAAB".


Finally:

  • A string w is dominated from both sides if both w and its reversal are prefix-dominated.

For example, the strings "ABACA" and "ABABAB" are both dominated from both sides while "ABAABBA" isn't (it is prefix-dominated by A but its reversal isn't prefix-dominated).


You are given an N-character string S (in the format specified below).

Find the length L of the longest contiguous substring of S that is dominated from both sides. Then, find the count C of such contiguous substrings of length L. (More precisely, C is the number of different indices into S where such a substring starts. I.e., identical substrings that appear at different positions in S still count as distinct occurrences.)

Return {L, C}.


In order to keep the input size small the string S is generated pseudorandomly. Please use the pseudocode below to generate it. 


state = seed
S = prefix
while length(S) < N:
    state = (state * 1103515245 + 12345) modulo 2^31
    value = (state div 32) modulo (pA + pB + pC)
    if value < pA:          S += 'A'
    if pA <= value < pA+pB: S += 'B'
    if pA+pB <= value:      S += 'C'

Definition

Class:
DominatedSubstrings
Method:
find
Parameters:
int, String, int, int, int, int
Returns:
int[]
Method signature:
int[] find(int N, String prefix, int seed, int pA, int pB, int pC)
(be sure your method is public)

Notes

  • The reference solution does not depend on the input being pseudorandom.

Constraints

  • N will be between 1 and 300,000, inclusive.
  • prefix will have between 0 and min(N, 2500) characters, inclusive.
  • Each character of prefix will be 'A', 'B', or 'C'.
  • seed will be between 0 and 2^31 - 1, inclusive.
  • pA, pB, pC will each be between 0 and 1,000,000, inclusive.
  • pA + pB + pC will not be zero.

Examples

  1. 6

    "ABABBA"

    47

    1

    1

    1

    Returns: {4, 2 }

    The full string S is given. The longest contiguous substrings of S that are dominated from both sides have length 4. There are two of them: one ("ABAB") starts at index 0, the other ("BABB") starts at index 1.

  2. 16

    "ABBABAABBABABBBA"

    42

    1

    1

    1

    Returns: {14, 1 }

    Here the unique longest contiguous substring of S that is dominated from both sides consists of everything except for the first and last letter of S.

  3. 30

    "ABACA"

    4742

    5

    5

    5

    Returns: {11, 1 }

    The full generated string S is "ABACACCBCABBCCBBCCBACCCABAACAA". The longest substring with the desired property is the substring "CCBBCCBACCC" which starts at index 12.

  4. 47000

    ""

    0

    1

    0

    0

    Returns: {47000, 1 }

    A string of 47,000 letters 'A'.

  5. 18

    "ABCABCABCABCABCABC"

    18

    18

    18

    18

    Returns: {2, 17 }

    Each substring of length 2 is dominated from both sides. No longer substring has the desired property. In a string of length 18 there are 17 two-letter substrings.

  6. 300000

    ""

    47

    24000

    47000

    24000

    Returns: {16831, 1 }

  7. 292260

    "CBCBCCCBCCBBCCBCCBBCBBBBBBBCBBBBB"

    946663796

    1

    6

    5

    Returns: {33172, 1 }

  8. 293658

    ""

    740909991

    6

    7

    1

    Returns: {41409, 1 }

  9. 291280

    "BCABACBCCCBCCBACACACBCCCBABABCCACCCCBCCBCACCCCBCBB"

    635153672

    2

    7

    5

    Returns: {58438, 1 }

  10. 296445

    ""

    467471973

    3

    9

    6

    Returns: {96527, 1 }

  11. 292254

    ""

    98988742

    8

    10

    3

    Returns: {2923, 1 }

  12. 292210

    "BCACBCCACCCACCCCACCCCCCCCAACCCBACCACCCCBBCCC"

    436568329

    6

    9

    4

    Returns: {1737, 1 }

  13. 293682

    ""

    57599824

    5

    6

    5

    Returns: {23, 574 }

  14. 290310

    ""

    541002364

    7

    4

    5

    Returns: {130, 567 }

  15. 291192

    "CBBBBABABBB"

    570819163

    4

    4

    5

    Returns: {126, 1 }

  16. 295051

    ""

    765308945

    10

    4

    1

    Returns: {295050, 1 }

  17. 290774

    ""

    513134692

    7

    5

    6

    Returns: {116, 2 }

  18. 295371

    "BABBACBBCCCAACAABAACBCCBABBCCCABCBBACBCBABABBCABCBAABACBCCACCACAACBBCBCACACBCAABBAACBBCBBCCBACCBBAA"

    621300276

    5

    4

    7

    Returns: {89, 577 }

  19. 298559

    "BCBCCCCCCCCCB"

    478108355

    771439

    262607

    540408

    Returns: {11215, 1 }

  20. 297894

    ""

    506331690

    942616

    270998

    738185

    Returns: {7438, 1 }

  21. 294056

    "BCABACBA"

    969078074

    116988

    792999

    725358

    Returns: {2522, 1 }

  22. 291397

    "ACACCCAACBAABACBAACCACAABAAAAAABCAAACAACABCBCACBCCCCBACBCACABABCCCCAACCBCBAAABCABCAACABAAAACCAC"

    878734777

    593778

    509749

    943513

    Returns: {597, 1 }

  23. 298109

    "CCCBBCBBAAAAAACCACBCCACABCBBA"

    962721868

    32660

    961074

    289034

    Returns: {298085, 1 }

  24. 300000

    ""

    1

    1

    0

    0

    Returns: {300000, 1 }

  25. 300000

    ""

    1

    0

    7

    0

    Returns: {300000, 1 }

  26. 300000

    ""

    1

    0

    0

    1000000

    Returns: {300000, 1 }

  27. 2499

    "CABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCAB"

    1

    1

    1

    1

    Returns: {2, 2498 }

  28. 1

    "A"

    1

    1

    1

    1

    Returns: {1, 1 }

  29. 1

    "B"

    1

    1

    1

    1

    Returns: {1, 1 }

  30. 1

    "C"

    1

    1

    1

    1

    Returns: {1, 1 }

  31. 2

    "AA"

    1

    1

    1

    1

    Returns: {2, 1 }

  32. 2

    "AB"

    1

    1

    1

    1

    Returns: {2, 1 }

  33. 2

    "AC"

    1

    1

    1

    1

    Returns: {2, 1 }

  34. 2

    "BA"

    1

    1

    1

    1

    Returns: {2, 1 }

  35. 2

    "BB"

    1

    1

    1

    1

    Returns: {2, 1 }

  36. 2

    "BC"

    1

    1

    1

    1

    Returns: {2, 1 }

  37. 2

    "CA"

    1

    1

    1

    1

    Returns: {2, 1 }

  38. 2

    "CB"

    1

    1

    1

    1

    Returns: {2, 1 }

  39. 2

    "CC"

    1

    1

    1

    1

    Returns: {2, 1 }

  40. 3

    "AAA"

    1

    1

    1

    1

    Returns: {3, 1 }

  41. 3

    "AAB"

    1

    1

    1

    1

    Returns: {2, 2 }

  42. 3

    "AAC"

    1

    1

    1

    1

    Returns: {2, 2 }

  43. 3

    "ABA"

    1

    1

    1

    1

    Returns: {3, 1 }

  44. 3

    "ABB"

    1

    1

    1

    1

    Returns: {2, 2 }

  45. 3

    "ABC"

    1

    1

    1

    1

    Returns: {2, 2 }

  46. 3

    "ACA"

    1

    1

    1

    1

    Returns: {3, 1 }

  47. 3

    "ACB"

    1

    1

    1

    1

    Returns: {2, 2 }

  48. 3

    "ACC"

    1

    1

    1

    1

    Returns: {2, 2 }

  49. 3

    "BAA"

    1

    1

    1

    1

    Returns: {2, 2 }

  50. 3

    "BAB"

    1

    1

    1

    1

    Returns: {3, 1 }

  51. 3

    "BAC"

    1

    1

    1

    1

    Returns: {2, 2 }

  52. 3

    "BBA"

    1

    1

    1

    1

    Returns: {2, 2 }

  53. 3

    "BBB"

    1

    1

    1

    1

    Returns: {3, 1 }

  54. 3

    "BBC"

    1

    1

    1

    1

    Returns: {2, 2 }

  55. 3

    "BCA"

    1

    1

    1

    1

    Returns: {2, 2 }

  56. 3

    "BCB"

    1

    1

    1

    1

    Returns: {3, 1 }

  57. 3

    "BCC"

    1

    1

    1

    1

    Returns: {2, 2 }

  58. 3

    "CAA"

    1

    1

    1

    1

    Returns: {2, 2 }

  59. 3

    "CAB"

    1

    1

    1

    1

    Returns: {2, 2 }

  60. 3

    "CAC"

    1

    1

    1

    1

    Returns: {3, 1 }

  61. 3

    "CBA"

    1

    1

    1

    1

    Returns: {2, 2 }

  62. 3

    "CBB"

    1

    1

    1

    1

    Returns: {2, 2 }

  63. 3

    "CBC"

    1

    1

    1

    1

    Returns: {3, 1 }

  64. 3

    "CCA"

    1

    1

    1

    1

    Returns: {2, 2 }

  65. 3

    "CCB"

    1

    1

    1

    1

    Returns: {2, 2 }

  66. 3

    "CCC"

    1

    1

    1

    1

    Returns: {3, 1 }

  67. 15

    "CCBCCCACABABCCA"

    1

    1

    1

    1

    Returns: {8, 1 }

  68. 17

    "CCCBACCCBBABCACCC"

    1

    1

    1

    1

    Returns: {8, 1 }

  69. 12

    "BCCACCBCBBCB"

    1

    1

    1

    1

    Returns: {8, 1 }

  70. 5

    "BBCAC"

    1

    1

    1

    1

    Returns: {3, 1 }

  71. 9

    "BBCAC"

    815758747

    7

    7

    7

    Returns: {3, 1 }

  72. 19

    "ABABCCAABCCCCBBACBC"

    1

    1

    1

    1

    Returns: {4, 4 }

  73. 20

    "BAAAABBAAACAAAABBBAB"

    1

    1

    1

    1

    Returns: {14, 1 }

  74. 7

    "BABABAA"

    1

    1

    1

    1

    Returns: {6, 2 }

  75. 10

    "BABABAA"

    389079416

    7

    7

    7

    Returns: {8, 1 }

  76. 20

    "CCCCAAAACBACAACAAABA"

    1

    1

    1

    1

    Returns: {16, 1 }

  77. 13

    "BCCBCCACCBCAA"

    1

    1

    1

    1

    Returns: {10, 1 }

  78. 17

    "CCAACACCCACCCABCC"

    1

    1

    1

    1

    Returns: {17, 1 }

  79. 21

    "CCAACACCCACCCABCC"

    756320184

    7

    7

    7

    Returns: {17, 1 }

  80. 14

    "BABBBBBBBCCABB"

    1

    1

    1

    1

    Returns: {9, 1 }

  81. 5

    "BAACC"

    1

    1

    1

    1

    Returns: {4, 1 }

  82. 19

    "BBCCACCAACBBBCBAACC"

    1

    1

    1

    1

    Returns: {6, 1 }

  83. 15

    "BCCCBCBCCCCCBBC"

    1

    1

    1

    1

    Returns: {11, 1 }

  84. 16

    "BCCCBCBCCCCCBBC"

    907833453

    7

    7

    7

    Returns: {15, 1 }

  85. 18

    "CABABAABBBBABCBABC"

    1

    1

    1

    1

    Returns: {10, 1 }

  86. 28

    "CABABAABBBBABCBABC"

    814584954

    7

    7

    7

    Returns: {10, 1 }

  87. 18

    "CBAACACABBAABACBAC"

    1

    1

    1

    1

    Returns: {12, 1 }

  88. 6

    "BBBBAC"

    1

    1

    1

    1

    Returns: {4, 1 }

  89. 7

    "BBCCCBC"

    1

    1

    1

    1

    Returns: {5, 1 }

  90. 20

    "BBAACBABCABABABCBCBB"

    1

    1

    1

    1

    Returns: {10, 1 }

  91. 7

    "CAACAAB"

    1

    1

    1

    1

    Returns: {5, 1 }

  92. 4

    "ACCB"

    1

    1

    1

    1

    Returns: {2, 3 }

  93. 10

    "ACCB"

    138066429

    7

    7

    7

    Returns: {6, 1 }

  94. 9

    "AAAAAAAAC"

    1

    1

    1

    1

    Returns: {8, 1 }

  95. 7

    "CBBACBA"

    1

    1

    1

    1

    Returns: {2, 6 }

  96. 11

    "CBBACBA"

    290923250

    7

    7

    7

    Returns: {4, 2 }

  97. 14

    "CCCCCCCBCCCBCB"

    1

    1

    1

    1

    Returns: {13, 1 }

  98. 17

    "AACAAACCAAAACAACC"

    1

    1

    1

    1

    Returns: {15, 1 }

  99. 17

    "CBAAACACBBACACBAA"

    1

    1

    1

    1

    Returns: {5, 1 }

  100. 13

    "BBBBBBBBBBBAC"

    1

    1

    1

    1

    Returns: {11, 1 }

  101. 13

    "CCCBACBBCAACA"

    1

    1

    1

    1

    Returns: {4, 1 }

  102. 15

    "BCAACAAAAACCABA"

    1

    1

    1

    1

    Returns: {8, 1 }

  103. 25

    "BCAACAAAAACCABA"

    25476197

    7

    7

    7

    Returns: {22, 1 }

  104. 12

    "BCABBACCCCBC"

    1

    1

    1

    1

    Returns: {6, 1 }

  105. 4

    "ACAA"

    1

    1

    1

    1

    Returns: {4, 1 }

  106. 5

    "ABBCB"

    1

    1

    1

    1

    Returns: {4, 1 }

  107. 7

    "ABBCB"

    652924993

    7

    7

    7

    Returns: {6, 1 }

  108. 13

    "CCBBBCCBCCBBA"

    1

    1

    1

    1

    Returns: {8, 1 }

  109. 23

    "CCBBBCCBCCBBA"

    411002003

    7

    7

    7

    Returns: {8, 1 }

  110. 8

    "AAAABABB"

    1

    1

    1

    1

    Returns: {6, 2 }

  111. 8

    "BCCAAACB"

    1

    1

    1

    1

    Returns: {4, 1 }

  112. 8

    "ACACBCCC"

    1

    1

    1

    1

    Returns: {7, 1 }

  113. 19

    "ABBBCAAAAABBCBBBABB"

    1

    1

    1

    1

    Returns: {9, 1 }

  114. 9

    "CCCCCCCCB"

    1

    1

    1

    1

    Returns: {8, 1 }

  115. 20

    "CAAACCAACCBACCCACCCC"

    1

    1

    1

    1

    Returns: {16, 1 }

  116. 24

    "CAAACCAACCBACCCACCCC"

    379249505

    7

    7

    7

    Returns: {16, 1 }

  117. 11

    "CCACCAABBCC"

    1

    1

    1

    1

    Returns: {6, 1 }

  118. 10

    "CACCAACCAC"

    1

    1

    1

    1

    Returns: {10, 1 }

  119. 6

    "CCAACB"

    1

    1

    1

    1

    Returns: {4, 1 }

  120. 11

    "CCAACB"

    768163270

    7

    7

    7

    Returns: {6, 1 }

  121. 7

    "BBBCCCB"

    1

    1

    1

    1

    Returns: {6, 1 }

  122. 5

    "CBAAC"

    1

    1

    1

    1

    Returns: {2, 4 }

  123. 12

    "AAACABBAABBB"

    1

    1

    1

    1

    Returns: {9, 1 }

  124. 19

    "AAACABBAABBB"

    49996629

    7

    7

    7

    Returns: {11, 1 }

  125. 8

    "BCBCBABC"

    1

    1

    1

    1

    Returns: {7, 1 }

  126. 6

    "BBAABB"

    1

    1

    1

    1

    Returns: {6, 1 }

  127. 7

    "CBABBCB"

    1

    1

    1

    1

    Returns: {6, 1 }

  128. 5

    "CBCCC"

    1

    1

    1

    1

    Returns: {5, 1 }

  129. 14

    "CBCACAABAACCCB"

    1

    1

    1

    1

    Returns: {7, 1 }

  130. 238626

    ""

    373260855

    14012

    23498

    37722

    Returns: {175890, 1 }

  131. 297953

    ""

    162206610

    47284

    25425

    22481

    Returns: {22359, 1 }

  132. 204612

    ""

    631946624

    26616

    31422

    58942

    Returns: {185193, 1 }

  133. 281473

    ""

    716796870

    7156

    50486

    42905

    Returns: {238784, 1 }

  134. 236998

    ""

    694843189

    15220

    43389

    29015

    Returns: {7407, 1 }

  135. 260254

    ""

    494413981

    31183

    11556

    20132

    Returns: {11988, 1 }

  136. 240499

    ""

    52944011

    3376

    15194

    18983

    Returns: {238210, 1 }

  137. 246602

    ""

    506952921

    1604

    43496

    42310

    Returns: {46624, 1 }

  138. 259520

    ""

    864142609

    4467

    35917

    30769

    Returns: {258698, 1 }

  139. 258096

    ""

    214138668

    13267

    29605

    17244

    Returns: {11617, 1 }

  140. 273123

    ""

    346279482

    2736

    36685

    39339

    Returns: {43484, 1 }

  141. 220779

    ""

    1058868246

    36059

    16622

    19062

    Returns: {213811, 1 }

  142. 266668

    ""

    474283356

    49660

    19005

    31132

    Returns: {32547, 1 }

  143. 299764

    ""

    961858595

    15810

    32537

    17661

    Returns: {14216, 1 }

  144. 296451

    ""

    694743143

    22241

    6555

    29287

    Returns: {283316, 1 }

  145. 282151

    ""

    774907183

    25281

    18055

    7165

    Returns: {84381, 1 }

  146. 218287

    ""

    385594653

    6159

    18733

    11789

    Returns: {216277, 1 }

  147. 279149

    ""

    614386108

    37404

    43391

    81048

    Returns: {76369, 1 }

  148. 205501

    ""

    211818701

    22008

    34340

    13155

    Returns: {29787, 1 }

  149. 239117

    ""

    292613055

    54187

    13802

    39841

    Returns: {212667, 1 }

  150. 231889

    ""

    975742368

    36285

    53290

    16759

    Returns: {211117, 1 }

  151. 203445

    ""

    374262968

    35133

    13353

    21254

    Returns: {189744, 1 }

  152. 235220

    ""

    531203019

    46194

    13366

    32910

    Returns: {45873, 1 }

  153. 252616

    ""

    107773563

    12735

    47588

    34243

    Returns: {241475, 1 }

  154. 228198

    ""

    574737088

    21653

    40975

    62452

    Returns: {86525, 1 }

  155. 282023

    ""

    657220750

    27397

    20842

    7084

    Returns: {13800, 1 }

  156. 230925

    ""

    988170459

    50665

    30915

    20384

    Returns: {7608, 1 }

  157. 237900

    ""

    81467142

    61719

    41102

    20099

    Returns: {217903, 1 }

  158. 286414

    ""

    314316586

    5494

    46733

    41012

    Returns: {276277, 1 }

  159. 249601

    ""

    955556853

    70442

    44128

    26203

    Returns: {235791, 1 }

  160. 300000

    "ABABBA"

    4723

    222

    111

    111

    Returns: {214572, 1 }

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.
This problem was used for: