CARDINAL - Editorial

PROBLEM LINKS

Practice
Contest

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 :slight_smile:

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.

6 Likes

great explanation! thanks.

great explanation! thanks.

The Tester’s solution to this question seems to be incorrect, at least for test case
N=3
A=1000000000 999999999 888888888,
the output is 2 but it should be 3

1 Like

Nice one …
Keep it up :slight_smile:

can anyone tell me the corner cases for this problem … I have checked with the tester’s solution …all the test cases that i have tried are giving the same output… Still getting WRONG ANSWER While submission…

Good catch! The method “adjust” should use long long for the “sum” instead of int.

can anyone explain how you check from complexity of algorithm and number of test cases whether time limit will be met

why have we taken values till 1024 only?

//