PROBLEM LINKS
DIFFICULTY
MEDIUM
PREREQUISITES
Dynamic Programming
PROBLEM
You are given a set of N positive integers A1, A2 …, AN. You wish to find a special subset of this set such that
- The numbers in the set have mutually exclusive set of digits
- The sum of the numbers is maximum among all such sets
- For sets with the same sum, the cardinality of the subset should be maximum
You have to print the cardinality of such a maximum sum special subset of the set given to you.
EXPLANATION
There are 2N subsets possible for a set of N elements.
Of course, in this problem, most of those 2N sets cannot be considered. This is because of the constraint that the numbers in the subset must have mutually exclusive set of digits.
In fact, a set will never have more than 10 numbers. Although, considering all sets of cardinality less than or equal to 10 is also impossible because there may simply be too many.
The key insight in this problem is that if we have two numbers made off the same set of digits, then we are always interested in the larger one. Hence, we never really have to consider more than 210 different numbers - since there are only 10 digits.
Of course, a set of digits can be represented by a bit set of 10 bits. Thus, we store the largest given number for each bit set.
We know that two bit sets can be combined if they don’t have a set bit for the same digit. This can be tested by a bitwise-and operation. If two bit sets can be combined, we will update the combined bit-set with the larger sum.
Just like the dynamic programming formulation for 0-1 knapsack we can maintain the largest sum for each bit set as follows
SUM[1 .. 1024] = {0}
for i = 1 to N
b = bitset for Ai
for m = 0 to 1024
if (m & b) = 0
SUMm+b = max(SUMm+b, SUMm + SUMb)
The above accomplishes finding the maximum sums for each bit set (with combined numbers) in O(N * 210) time.
This is sufficient to solve the problem. This approach is used in the setter’s as well as tester’s code.
There is an alternate way to solve the problem though that is slightly faster for N ≥ 50. It utilises the fact that we don’t need to consider the numbers one by one.
The dynamic programming formulation works just as well if we consider them all at once. If we resolve the final answers for the bit sets from smaller ones to larger ones, then we ensure that the dynamic program above works in the following code.
Consider the pseudo-code below
SUM[1 .. 1024] = {0}
//mark 1
for i = 1 to N
b = bitset for Ai
SUMb = max(SUMb,Ai)
//mark 2
for m = 0 to 1024
S = set of set bits in m
for each subset s of S
t = bit set representing s
SUMm = max(SUMm, SUMt + SUMm-t)
The complexity of the section right after mark 1 in the above pseudo-code is obviously O(N).
The complexity of the section right after mark 2 in the above pseudo-code is O(310). The proof of this complexity is left as an exercise to the reader 
CODE COMMENTARY
Till now, we have not talked about cardinality at all. This is because solving the problem to find the cardinality is just a small step above the solution described above.
We already know how to find the maximum sum.
We can maintain another array to store the cardinality of that maximum sum. Whenever we try to relax the sum with the same value, we must relax cardinality as well.
SETTER’S SOLUTION
Can be found here.
TESTER’S SOLUTION
Can be found here.