RandomConcat
TCO19 SRM 742 · 2018-11-27 · by misof
Problem Statement
You have several (at most 15) strings in the
You also have a
Notes
- Your return value must have an absolute or a relative error at most 1e-9.
Constraints
- pieces will have between 1 and 15 elements, inclusive.
- Each element of pieces will have between 1 and 50 characters, inclusive.
- needle will have between 1 and 50 characters, inclusive.
- Each character in each of the strings will be a lowercase English letter ('a'-'z').
{"hahaha"}
"aha"
Returns: 2.0
Haystack will always be "hahaha". This string contains two occurrences of the string "aha". Note that the two occurrences overlap partially.
{"hah","ah"}
"aha"
Returns: 0.5
With probability 1/2 haystack will be "hahah" and there is one occurrence of the substring "aha". With probability 1/2 haystack will be "ahhah" and there are no occurrences of "aha". Hence, the expected number of occurrences is 0.5.
{"t","o","p","c","o","d","e","r"}
"topcoder"
Returns: 4.9603174603174596E-5
Two of the 8! permutations produce the haystack "topcoder" that exactly matches the given needle.
{"hellotopc","oderhellotop","coderbye"}
"topcoder"
Returns: 0.6666666666666666
If we concatenate the pieces in the given order, there will be two occurrences of "topcoder". Two other concatenation orders will produce a haystack with one occurrence of the needle, and the remaining three produce a haystack that contains no needles at all.
{"aabaa","aabaaaaa","aba","goodluck","havefun"}
"aaaa"
Returns: 2.8000000000000016
Submissions are judged against all 194 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class RandomConcat with a public method double expectation(vector<string> pieces, string needle) · 194 test cases · 2 s / 256 MB per case