DominatedSubstrings
TCO22 Wildcard · 2022-04-14 · by misof
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'
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.
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.
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.
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.
47000
""
0
1
0
0
Returns: {47000, 1 }
A string of 47,000 letters 'A'.
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.
Submissions are judged against all 160 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class DominatedSubstrings with a public method vector<int> find(int N, string prefix, int seed, int pA, int pB, int pC) · 160 test cases · 2 s / 256 MB per case