BestTestPattern
SRM 854 · 2024-04-24 · by misof
Problem Statement
A class full of lazy students is about to take a multiple choice test. The test awards 1 point for each correct answer. There is no penalty for giving a wrong answer.
None of the students prepared for the test, so everyone decided to just pick a specific pattern of answers and repeat it on their entire answer sheet. For example, the student who picked the pattern "AACB" will answer the questions on the test as follows: A, A, C, B, A, A, C, B, A, A, C, B, and so on.
For each possible pattern of each possible length between 1 and maxLen, inclusive, there is some student who has picked that specific pattern.
You are given the
Determine and return the pattern of answers that scored the most points on this test. If there are multiple optimal answers, return the lexicographically smallest among them (see Notes for definition).
Notes
- In most programming languages, the lexicographic order of strings corresponds to the built-in string comparison operator "less than".
- Formally, given two different strings S and T, we say that S is lexicographically smaller than T if either S is a proper prefix of T, or for some i the characters S[i] and T[i] differ, and for the smallest such i the character S[i] is smaller than the character T[i].
- For example, "CAR" is smaller than "CARBON" because it's the proper prefix of "CARBON", and S = "CAR" is smaller than T = "CELL" because S[1]='A' which is smaller than T[1]='E'.
Constraints
- correctAnswers will have between 1 and 3,000 characters, inclusive.
- Each character in correctAnswers will be an uppercase letter between 'A' and 'F', inclusive.
- maxLen will be between 1 and the number of characters in correctAnswers, inclusive.
"AACAAACBAACA" 5 Returns: "AACA"
The student who picked the pattern "AACA" will get 11 out of 12 possible points. Among the allowed patterns this is the only optimal one for this particular test.
"ABCABCAB" 3 Returns: "ABC"
The length of the pattern does not have to divide the length of the test. Here, the student who picked the pattern "ABC" will answer the entire test correctly.
"FCFBFAFDFEFCFBFEFDF" 4 Returns: "FAFB"
Here the most points any student can score is 12. There are many patterns that score this number of points. Among the optimal patterns there are some of length 2 (these are "FB", "FC", "FD", and "FE") and some of length 4. The lexicographically smallest among all optimal patterns is "FAFB". In particular, note that "FAFB" < "FB".
"EEEEEEE" 3 Returns: "E"
Here the patterns "E", "EE", and "EEE" all give you full score, and "E" is the lexicographically smallest among them.
"AACAAACBAACA" 3 Returns: "A"
The same test as in Example 0, but now patterns of length 4 aren't allowed.
Submissions are judged against all 118 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class BestTestPattern with a public method string solve(string correctAnswers, int maxLen) · 118 test cases · 2 s / 256 MB per case