PrefixFreeSuperset
TCO11 Round 3 · 2011-05-07 · by soul-net
Problem Statement
A prefix of a string s is any string that can be obtained by erasing zero or more characters from the right end of s. A prefix-free set is a set of binary words in which no element is a prefix of another element in the set. For example {"00"} , {"00", "01", "110", "10"} and the empty set are examples of prefix-free sets. On the other hand, {"0","01"} and {"111","11","1"} are not prefix-free.
You will be given a
Constraints
- cur will contain between 1 and 50 elements, inclusive.
- Each element of cur will contain between 1 and 50 characters, inclusive.
- Each character of each element of cur will be either '0' (zero) or '1' (one).
- No element of cur will be a prefix of another element of cur.
- k will be between the number of elements in cur and 1000000000000 (10^12), inclusive.
{"010"}
4
Returns: 9
One optimal possibility is the set {"010","1","00","011"}
{"01","000"}
4
Returns: 9
The set {"000","01","10","11"} is prefix-free and includes all the words in cur, so it is a possible answer. The sum of the lengths of the words in that set is also minimal.
{"0011","011110101","11101010111","11101010100000000","11101010100000001111"}
1000000000000
Returns: 39971901640560
{"010","00","011","1"}
4
Returns: 9
{"010","00","011","1"}
5
Returns: -1
Submissions are judged against all 107 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class PrefixFreeSuperset with a public method long long minSumLength(vector<string> cur, long long k) · 107 test cases · 2 s / 256 MB per case