ProductBundling

SRM 324 · 2006-10-25 · by AdrianKuegel

SRM 324 · 2006-10-25 · by AdrianKuegel · Greedy, Simple Search, Iteration

Show categories

Class Name: ProductBundling

Return Type: int

Method Name: howManyBundles

Arg Types: (vector<string>)

Problem Statement

A company wants to generate cost advantage by bundling its products, which means that several products are sold in a package. In order to compose bundles optimally, the company has collected data about which products were bought from customers.

Your company produces n products. You will be given a String[] data, each element of which contains exactly n characters. The j^th character of element i of data will be '1' if customer i bought product j, and '0' otherwise. Two products can be in the same bundle only if every customer bought neither of them or both of them. It is possible for a bundle to contain just one product. Return the minimum number of bundles into which the products can be partitioned. Note that every product must be put in some bundle.

Constraints

data will contain between 1 and 50 elements, inclusive.
Each element of data will contain between 1 and 50 characters, inclusive.
Each element of data will contain the same number of characters.

Examples

{"11100"}
Returns: 2

In this example, only data from one customer is available. Two bundles can be composed, the first containing the first three products, the second containing the last two products.

{"1010",
 "1100"}
Returns: 4

No two products can be put into the same bundle, therefore 4 bundles are needed.

{"1100000000",
 "1100000000",
 "0011000000",
 "0011000000",
 "0000110000",
 "0000110000",
 "0000001100",
 "0000001100",
 "0000000011",
 "0000000011"}
Returns: 5

{"10101010101010101010101010101010101010101010101010","11001100110011001100110011001100110011001100110011","11110000111100001111000011110000111100001111000011","11111111000000001111111100000000111111110000000011","11111111111111110000000000000000111111111111111100","11111111111111111111111111111111000000000000000000","11111111111111111111111111111111111111111111111111","11111111111111111111111111111111111111111111111111","11111111111111111111111111111111111111111111111111","11111111111111111111111111111111111111111111111111","11111111111111111111111111111111111111111111111111","11111111111111111111111111111111111111111111111111","11111111111111111111111111111111111111111111111111","11111111111111111111111111111111111111111111111111","11111111111111111111111111111111111111111111111111","11111111111111111111111111111111111111111111111111","11111111111111111111111111111111111111111111111111","11111111111111111111111111111111111111111111111111","11111111111111111111111111111111111111111111111111","11111111111111111111111111111111111111111111111111","11111111111111111111111111111111111111111111111111","11111111111111111111111111111111111111111111111111","11111111111111111111111111111111111111111111111111","11111111111111111111111111111111111111111111111111","11111111111111111111111111111111111111111111111111","11111111111111111111111111111111111111111111111111","11111111111111111111111111111111111111111111111111","11111111111111111111111111111111111111111111111111","11111111111111111111111111111111111111111111111111","11111111111111111111111111111111111111111111111111","11111111111111111111111111111111111111111111111111","11111111111111111111111111111111111111111111111111","11111111111111111111111111111111111111111111111111","11111111111111111111111111111111111111111111111111","11111111111111111111111111111111111111111111111111","11111111111111111111111111111111111111111111111111","11111111111111111111111111111111111111111111111111","11111111111111111111111111111111111111111111111111","11111111111111111111111111111111111111111111111111","11111111111111111111111111111111111111111111111111","11111111111111111111111111111111111111111111111111","11111111111111111111111111111111111111111111111111","11111111111111111111111111111111111111111111111111","11111111111111111111111111111111111111111111111111","11111111111111111111111111111111111111111111111111","11111111111111111111111111111111111111111111111111","11111111111111111111111111111111111111111111111111","11111111111111111111111111111111111111111111111111","11111111111111111111111111111111111111111111111111","11111111111111111111111111111111111111111111111111"}
Returns: 50

{"01110100010010010100100011000010110010011101101101","10001011101101101011011101011111011110101011011011","10001110011100000000010111101000000000000110110110","01110101110011111111101010011111011110101110110110","00000000000000000000000011110011011011011101101101","11111111111111111111111111111111011111111111111111","11111010000110010100110100000001001001000000000000","01110100010010010100100000000000000000000000000000","00000001101001101011001111011011111011001001010000","11111111111111111111111011001110010110111000010000"}
Returns: 21

Submissions are judged against all 71 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class ProductBundling with a public method int howManyBundles(vector<string> data) · 71 test cases · 2 s / 256 MB per case