So this problem came up when I was trying to calculate the maximum number of people that are all available for $$$k$$$ hours. Essentially the $$$j$$$-th bit of $$$a_i$$$ represents the availability of the $$$j$$$-th person at hour $$$i$$$. I am wondering if there is an efficient solution to this. Formally one could define the problem as follows:
The "score" of a number $$$x$$$ is defined as the number of 1s in the binary representation of $$$x$$$. For example, the score of 5 is 2, since 5 is 101 in binary.
You are given a list $$$A$$$ of $$$n$$$ integers: $$$0\leq a_1$$$, $$$a_2$$$, $$$a_3$$$, ..., $$$a_n\leq 2^{20}$$$. You are given an integer $$$k$$$ ($$$1\leq k\leq n$$$).
Your task is to choose exactly $$$k$$$ unique integers: $$$1 \leq$$$ $$$i_1$$$, $$$i_2$$$, ... $$$i_k$$$ $$$\leq n$$$, so that the "score" of the bitwise AND of $$$a_{i_1}, a_{i_2}, ... , a_{i_k}$$$ is maximum.
Print the integers $$$i_1$$$, $$$i_2$$$, ... $$$i_k$$$. If there are multiple answers, print any of them.
Any ideas on how to solve this?
So lets reframe the problem to "finding the largest value $$$x$$$ such that there are at least k integers such that their bitwise and is $$$x$$$". Then lets also use a very useful property of powers of 2, which is that $$$2^k > \sum_{i = 0}^{k-1} 2^i$$$. So it is much more important to get a higher bit than any amount of lower bits.
With both of these in mind, let's construct the maximum $$$x$$$.So consider the highest bit, if there are at least $$$k$$$ values that have that bit on, then you should take that bit. If not, don't worry about that bit and see if you can secure lower bits. Say, there are at least k values that have the highest bit. Now try the second highest bit. Out of all the numbers that have the highest bit on, are there k of them that have the second highest? If so, take it, if not, don't take it.
To construct the answer, just loop over the array in the end and take all supermasks of x, or all values such arr[i] such that $$$ arr_i$$$ & $$$x == x$$$ .
I think I didn't make the problem clear enough. Sorry for that.
Let me clarify.
If for instance we have $$$n=4$$$, $$$k=2$$$, and $$$A=1000,1001,0111,0110$$$, then the highest score would be 2, if we choose $$$0111$$$ and $$$0110$$$, the bitwise and is $$$0110$$$, and there are 2 1s.
With the way you reframed it, it would be $$$1000$$$ and $$$1001$$$, whose bitwise and is $$$1000$$$, thus the score is 1, because there is only 1 set bit. The bitwise and is a bigger number, but what I care about is the number of bits set.
ohhh so I misread, my bad.
This problem can be solved using SOS dp (Sum Over Subsets dp).
Let's define $$$dp[i]$$$ to be the number of elements in the input array that are a supermask of $$$i$$$, for $$$0$$$ <= $$$i$$$ <= $$$2^{20}$$$
We can use the recurrences mentioned in the sos dp blog to compute the dp array. (I'm not explaining the recurrences here because they have already been explained in the blog)
Now, notice that if $$$x$$$ elements in the array are a supermask of $$$i$$$, then the maximum size of a set with bitwise AND >= $$$i$$$ is $$$x$$$. So we must find the maximum value of $$$setbits(i)$$$ for all values of $$$i$$$ such that $$$dp[i] >= k$$$. This would be the maximum possible score. We pick an arbitrary value of $$$i$$$ that gives us this maximum score and make that be the bitwise AND of the chosen set. Let's call this value $$$val$$$.
To build the final set of values, just iterate over all elements of the input array and pick any $$$k$$$ of these elements that are a supermask of $$$val$$$.
The time complexity would be $$$O(n + 20 * 2^{20})$$$
Wow! Interesting technique.
It's a little bit over my head right now, but I'll try to figure it out and implement it.
Thank you!