IndependentOfOR
TCO12 Semifinal 2 · 2012-03-27 · by cgy4ever
TCO12 Semifinal 2 · 2012-03-27 · by cgy4ever · Greedy, Math, Search
Problem Statement
Problem Statement
Let S be a set containing k non-negative integers: { S[0], ..., S[k-1] }.
We define OR(S) to be the bitwise "or" of all elements of S.
Formally:
OR(S) = S[0] or S[1] or ... or S[k-1].
For consistency, if S is the empty set, then OR(S) is defined to be 0.
A set T is called "independent with respect to OR" if no two subsets of T produce the same value when OR is applied to them. Formally, T should have the following property: | { OR(S) : S is a subset of T } | = 2^|T|. In words: the set of all values OR(S), where S is a subset of T, contains exactly (2 to the size of T) distinct values.
You are given aint[] A that describes a set of integers.
Your goal is to select a subset B of the set described by A.
The subset B has to be independent with respect to OR, and the sum of its elements has to be as large as possible.
Return the largest possible sum of elements of the set B.
A set T is called "independent with respect to OR" if no two subsets of T produce the same value when OR is applied to them. Formally, T should have the following property: | { OR(S) : S is a subset of T } | = 2^|T|. In words: the set of all values OR(S), where S is a subset of T, contains exactly (2 to the size of T) distinct values.
You are given a
Constraints
- A will contain between 1 and 50 elements, inclusive.
- All elements of A will be pairwise distinct.
- Each element in A will be between 1 and 1,000,000, inclusive.
Examples
0)
{2, 3}
Returns: 3
The optimal solution is: {3}. Note that {2, 3} is not a valid solution, since |OR({2, 3})| = |{0, 2, 3}| = 3 < 2^2 = 4.
1)
{1, 2, 3, 4, 5, 6}
Returns: 11
This time the optimal solution is {5, 6}.
2)
{2, 3, 5, 7, 11, 13, 17, 19}
Returns: 41
3)
{8, 9, 13, 45, 47, 111, 127}
Returns: 127
4)
{5, 8, 55, 58, 85, 88, 555, 558, 585, 588, 855, 858, 885, 888}
Returns: 2919
Submissions are judged against all 143 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class IndependentOfOR with a public method int maxSum(vector<int> A) · 143 test cases · 2 s / 256 MB per case