MonotoneStrings
SRM 811 · 2021-08-19 · by misof
Problem Statement
This is a string problem.
In the problem we are using an alphabet of size S.
Let V be the string of length 62 of the form "a-zA-Z0-9": first all lowercase English letters, then all uppercase letters, and finally all digits.
If S <= 62, the alphabet is a prefix of the string V. For example, if S = 5, our alphabet contains the letters 'a', 'b', 'c', 'd', and 'e'.
If S > 62, V is a prefix of the alphabet. In that case, the other characters of the alphabet do not matter, all that you need to know about them is that all characters in the alphabet are distinct. For example, if S = 65, our alphabet consists of all characters of V + three additional unique characters.
A string Z is called monotone if Z[i] = Z[j] implies Z[i] = Z[k] = Z[j] for all k between i and j.
For example, "aaaaaargh", "bad", and "toffee" are monotone but "teeth" isn't: for Z = "teeth" we have Z[0] = Z[3] = 't' but Z[2] = 'e' differs from Z[0] and Z[3].
We will consider three types of wildcards: '?' matches a single character, '-' (minus) matches exactly 10 characters, and '+' matches exactly 100 characters.
For example, the pattern "l-n" matches the string "localization", and the pattern "t????e" matches the string "toffee".
You are given the alphabet size S and a
Count all monotone strings that match the given pattern. Return that count modulo 1,000,000,007.
Notes
- As one would expect, for S > 62 the additional characters in the alphabet are also distinct from the three wildcards.
Constraints
- S will be between 1 and 400, inclusive.
- pattern will have between 1 and 2500 characters, inclusive.
- Each character in pattern will be a character of V or a wildcard.
- Each character in pattern that is not a wildcard will be a valid character of the S-character alphabet.
26 "te?th" Returns: 0
There are 26 different strings that match the given pattern but clearly none of those strings is a monotone string.
1 "++++++++++" Returns: 1
The only string that matches this pattern is a string of 1000 'a's. That string is monotone, so the answer is 1.
4 "++++++++++++++++++++" Returns: 952039775
The exact answer for this test case is 31,952,039,992. The return value is the remainder this number gives modulo 1,000,000,007.
370 "?4?" Returns: 136531
There are many strings like "x4y", some strings like "x44", some like "44x", and finally there is the string "444".
5 "?a??b??a?" Returns: 0
30 "ll??as" Returns: 786
Not all 30*30 strings that match this pattern are monotone. For example, "llamas" isn't monotone. On the other hand, "llAmas" is a valid monotone string that matches the given pattern, as 'A' and 'a' are two different characters. "llAMas" is not a valid string at all, as 'M' is not in the 30-character alphabet. The alphabet contains all lowercase letters, 'A', 'B', 'C', and 'D'.
62 "+q+w+e+r+t+y+u+i+o+p+a+s+d+f+g+h+j+k+l+z+x+c+v+b+n+m+Q+W+E+R+T+Y+U+I+O+P+A+S+D+F+G+H+J+K+L+Z+X+C+V+B+N+M+0+1+2+3+4+5+6+7+8+9+" Returns: 184156089
(101^61) % 1000000007
63 "q+w+e+r+t+y+u+i+o+p+a+s+d+f+g+h+j+k+l+z+x+c+v+b+n+m+Q+W+E+R+T+Y+U+I+O+P+A+S+D+F+G+H+J+K+L+Z+X+C+V+B+N+M+0+1+2+3+4+5+6+7+8+9" Returns: 860223612
(101^61) + 61 * (101^60) * comb(101,2)
Submissions are judged against all 98 archived test cases, of which 8 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class MonotoneStrings with a public method int count(int S, string pattern) · 98 test cases · 2 s / 256 MB per case