MixingColors
SRM 621 · 2013-12-22 · by boba5551
Problem Statement
Danica is an artist. She would like to paint a picture, but currently she has no colors at all.
For the purpose of this problem, colors are represented by positive integers. You are given a
There is a store that sells colors. The store has an unlimited supply of all possible colors, including colors that Danica doesn't need. Danica will buy some colors in the store. Then, she will produce other colors by mixing the colors she bought.
Danica can only mix two colors at a time. Mixing two different colors A and B produces the color (A XOR B). Colors obtained by mixing can later be used to produce other colors.
Danica wants to buy as few distinct colors as possible. Note that she is allowed to buy colors she does not need for the picture.
Return the smallest number of distinct colors Danica has to buy in order to be able to obtain all the colors she needs.
Notes
- XOR (exclusive or) is a binary operation, performed on two numbers in binary notation. First, the shorter number is prepended with leading zeroes until both numbers have the same number of digits (in binary). Then, the result is calculated as follows: for each bit where the numbers differ the result has 1 in its binary representation. It has 0 in all other positions.
- For example 15 XOR 55 is performed as follows. First, the numbers are converted to binary: 15 is 1111 and 55 is 110111. Then the shorter number is prepended with leading zeros until both numbers have the same number of digits. This means 15 becomes 001111. Then 001111 XOR 110111 = 111000 (the result has ones only in the positions where the two numbers differ). Then the result can be converted back to decimal notation. In this case 111000 = 56, so 15 XOR 55 = 56.
Constraints
- colors will contain between 1 and 50 elements, inclusive.
- Each element of colors will be between 1 and 1,000,000,000, inclusive.
- All elements of colors will be distinct.
{1, 7, 3}
Returns: 3
Obviously, Danica can just buy the three colors she needs. However, there are also other optimal solutions. For example, she could buy colors 1, 2, and 4 instead. Then, she can mix these colors as follows: She already has color 1. She can obtain color 3 by mixing colors 1 and 2: we have 1 XOR 2 = 3. She can obtain color 7 by first mixing colors 1 and 4 to produce color 5 (as 1 XOR 4 = 5), and then mixing colors 5 and 2 (as 5 XOR 2 = 7).
{10}
Returns: 1
Danica should buy color 10 only.
{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15}
Returns: 4
Danica can, for instance, buy colors 11, 13, 14, and 15.
{534, 251, 76, 468, 909, 410, 264, 387, 102, 982, 199, 111, 659, 386, 151}
Returns: 10
{4, 8, 16, 32, 64, 128, 256, 512, 1024}
Returns: 9
Submissions are judged against all 129 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class MixingColors with a public method int minColors(vector<int> colors) · 129 test cases · 2 s / 256 MB per case