Any ideas of how to solve this problem that showed up in real life.

Правка en2, от robchik, 2022-05-04 05:04:01

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?

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский robchik 2022-05-04 05:04:01 0 (published)
en1 Английский robchik 2022-05-04 05:03:44 1026 Initial revision (saved to drafts)