TopCoder problem "BitStrings" used in SRM 248 (Division II Level Three)



Problem Statement

    You are given a list of bitstrings (i.e. strings consisting of only 0's and 1's). You also have a number of 0's and 1's at your disposal. You want to know the maximum number of bitstrings in the list that you can create using those 0's and 1's. Of course, once you use a zero or one, you cannot use it again.



Create a class BitStrings that contains a method maxStrings. maxStrings takes a String[] list, an int numZeroes and an int numOnes as input. The method should return the maximum number of strings from list that can be created using numZeroes zeroes and numOnes ones. Again, reusing zeroes and ones is not allowed.
 

Definition

    
Class:BitStrings
Method:maxStrings
Parameters:String[], int, int
Returns:int
Method signature:int maxStrings(String[] list, int numZeroes, int numOnes)
(be sure your method is public)
    
 

Constraints

-list will contain between 2 and 20 elements inclusive.
-Each element of list will have a length between 1 and 50 inclusive.
-Each element of list will contain only the characters '0' and '1'.
-numZeroes and numOnes will each be between 0 and 500 inclusive.
 

Examples

0)
    
{"1", "00", "100"}
3
1
Returns: 2
Here, you have three 0's and one 1 at your disposal. The best you can do is create the first two bitstrings. Note that if you create the third bitstring, then you cannot construct any other bitstrings because you won't have a sufficient number of 0's and 1's.
1)
    
{"00", "110", "101"}
2
4
Returns: 2
In this case, you have 2 0's and 4 1's. Although you can make the first bitstring "00", you then run out of zeroes and cannot make any more; in this case, you can only construct 1 bitstring. You can do better if you leave the first bitstring and construct the last two, giving a final answer of 2.
2)
    
{"111", "01", "11", "10", "101"}
3
9
Returns: 5
3)
    
{"10101010101010101010101010101010101010101010101010",
"10101010101010101010101010101010101010101010101010",
"10101010101010101010101010101010101010101010101010",
"10101010101010101010101010101010101010101010101010",
"10101010101010101010101010101010101010101010101010",
"10101010101010101010101010101010101010101010101010",
"10101010101010101010101010101010101010101010101010",
"10101010101010101010101010101010101010101010101010",
"10101010101010101010101010101010101010101010101010",
"10101010101010101010101010101010101010101010101010",
"10101010101010101010101010101010101010101010101010",
"10101010101010101010101010101010101010101010101010",
"10101010101010101010101010101010101010101010101010",
"10101010101010101010101010101010101010101010101010",
"10101010101010101010101010101010101010101010101010",
"10101010101010101010101010101010101010101010101010",
"10101010101010101010101010101010101010101010101010",
"10101010101010101010101010101010101010101010101010",
"10101010101010101010101010101010101010101010101010",
"10101010101010101010101010101010101010101010101010"}
500
500
Returns: 20

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=3545

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=7223&pm=3545

Writer:

NeverMore

Testers:

PabloGilberto , lbackstrom , brett1479

Problem categories:

Dynamic Programming