AllInclusiveString
TCO19 SRM 751 · 2019-01-09 · by majk
Problem Statement
This problem has an unusual time limit: 5 seconds.
You are given the
We call a string S all-inclusive if it contains every string from a as a (not necessarily contiguous) subsequence.
For example, if a={"ab","cd"}, then strings "abcd", "acbd" and "babcde" are all-inclusive, but strings "bacd" and "abab" are not.
Let L be the length of the shortest all-inclusive string, and C the number of all-inclusive strings of length exactly L. Return a
Notes
- .
Constraints
- a contains between 0 and 256 elements, inclusive.
- Each element of a is a string of length 2, consisting of characters 'a' to 'p'.
- All elements of a are distinct
{"aa", "ac"}
Returns: {3, 2 }
There are exactly two all-inclusive strings of length 3, "aac" and "aca". There are no shorter all-inclusive strings.
{}
Returns: {0, 1 }
An empty string is all-inclusive.
{"aa", "bb", "cc"}
Returns: {6, 90 }
An all-inclusive string of length 6 contains 2 of each characters 'a', 'b' and 'c' in any order, the answer is thus 6!/2!2!2!.
{"ac","ag","aj","bb","bf","bg","bh","ce","cg","da","de","df","dg","di","ea","eb","ef","ei","fb","fc","fg","gc","gf","gi","gj","hb","hh","hi","ib","ih","ij","jj"}
Returns: {15, 11461680 }
{"ab","ag","ai","aj","ba","bb","bc","bd","bf","bg","bh","ca","cb","cc","cd","ce","cg","ch","ci","cj","da","dc","de","df","dg","dh","di","dj","ea","ec","ed","ee","ei","ej","fa","fc","ff","fg","fh","fi","ga","gb","gc","gf","gg","hb","hd","he","hg","hh","hi","hj","ia","ic","id","ie","ih","ii","ja","jb","jc","jd","jg","jh"}
Returns: {18, 930902781 }
Submissions are judged against all 91 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class AllInclusiveString with a public method vector<int> shortest(vector<string> a) · 91 test cases · 2 s / 256 MB per case