Strcmp
TCO 22 Semi 1 · 2022-11-17 · by misof
Problem Statement
Time limit: 6 seconds.
Standard libraries of many programming languages contain the function strcmp: a simple function that compares two strings.
The implementation of this function is trivial: it starts at the beginning of both strings and then performs a sequence of character comparisons until it can determine how the strings compare within the lexicographic order.
Thus, for example:
- strcmp("cat", "dog") will perform 1 character comparison: after we compare 'c' to 'd' we can be sure that "cat" < "dog".
- strcmp("cat", "cougar") will perform 2 character comparisons: first we compare 'c' to 'c' and then 'a' to 'o'.
- strcmp("cat", "cat") will perform 3 character comparisons, after which we conclude that the two strings are equal.
- strcmp("catch", "cat") will perform 3 character comparisons, after which we observe that the first string still continues while the second one terminated, and we conclude that "catch" > "cat".
Given a collection of X (not necessarily distinct) strings, their similarity is the total number of character comparisons performed when we run strcmp on each (unordered) pair of strings from our collection.
For example, the collection { "", "cat", "cat", "cougar" } has similarity = 0+0+0+3+2+2 = 7, and if we add "dog" to the collection, its similarity will become 10.
Given are the constraints N, L, and S with the following meaning:
- We only consider collections of exactly N strings.
- The length of each string in the collection must be between 0 and L, inclusive.
- Each character in each string in the collection must be one of the first S lowercase English letters.
An integer X is called good if and only if there is a valid collection with similarity exactly X.
You are given a range: integers A and B. Your task is to do the following steps:
- Compute Y = the number of all good integers in the range [A, B].
- Determine whether A is a good integer.
- If it is, construct one proof: a valid collection of strings with similarity exactly A.
If A is bad, return a
If A is good, return a
Notes
- Above, str(Y) denotes the string containing the base-10 representation of Y with no unnecessary leading or trailing zeros. For example, str(47) = "47" and str(0) = "0".
Constraints
- N will be between 1 and 50, inclusive.
- L will be between 1 and 50, inclusive.
- S will be between 1 and 26, inclusive.
- A will be between 0 and 10^9, inclusive.
- B will be between A and 10^9, inclusive.
4
1
1
0
10
Returns: {"4", "a", "", "", "" }
N=4 strings, each with at most L=1 character, and as S=1, the only allowed character is 'a'. There are five essentially different collections of strings we can have: { "", "", "", "" }: similarity 0 { "", "", "", "a" }: similarity 0 { "", "", "a", "a" }: similarity 1 { "", "a", "a", "a" }: similarity 3 { "a", "a", "a", "a" }: similarity 6 Hence, the range [0,10] contains four good numbers: 0, 1, 3, and 6. The value A=0 is good, so we return not just the number "4" but also one collection of four strings with similarity 0.
1
40
26
1
1000000000
Returns: {"0" }
Regardless of which one string (of up to 40 arbitrary lowercase letters) we choose, our collection will have similarity 0: there are no pairs of strings and thus no comparisons performed. The range [1,10^9] contains no good numbers, and in particular the value 1 is not good so we don't construct a solution.
4
3
4
11
20
Returns: {"5" }
The good values in this range are 12, 13, 14, 15, and 18. As 11 is not good, we don't do the construction.
4
3
4
12
20
Returns: {"5", "cdb", "cdc", "cdd", "ddd" }
Essentially the same test case as in the previous example, but as now A = 12 is a good number, the correct return value must contain one valid collection of strings with similarity 12.
5
5
2
27
27
Returns: {"1", "baaab", "baabb", "baa", "babbb", "bbbbb" }
The collection {"baaaa", "baaa", "baa", "baa", "bbbbb"} has similarity 27: When comparing its element 0 ("baaaa") to the following elements we make 4, 3, 3, 2 comparisons. When comparing its element 1 ("baaa") to the following elements we make 3, 3, 2 comparisons. When comparing its element 2 ("baa") to the following elements we make 3, 2 comparisons. When comparing its element 3 ("baa") to the following element we make 2 comparisons. The total number of comparisons is 4+3+3+2+3+3+2+3+2+2 = 27.
Submissions are judged against all 174 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class Strcmp with a public method vector<string> construct(int N, int L, int S, int A, int B) · 174 test cases · 2 s / 256 MB per case