Número máximo tras la suma de la operación AND

Question

Se le da una matriz de N números digamos [A1,A2,⋯An]. Definamos una función F(x)=∑i=1 a n (Ai&x) donde & es el operador AND a nivel de bits. Necesitamos encontrar el número de valores diferentes de x para los que el valor de F(x) es maximizado. Pero hay una restricción para x que debe tener exactamente L bits-set en su representación binaria. Además, imprime -1 si hay un número infinito de X posibles que cumplan la restricción

Por ejemplo, si la matriz es [3,5,7,1,4] y L=2, la respuesta es 2, porque 5 y 6 son números con 2 bits fijos en su representación binaria y dan el máximo valor después de realizar (A1&x)+(A2&x)+(A3&x)+⋯+(An&x). Así que los valores de x son 5 y 6 y la respuesta es 2.

Otro ejemplo es que el array es [3,5,7,1,4] y L=1 entonces la respuesta es 1 porque sólo x=4 satisface las restricciones.

Answer 1

Dejemos que $A_1,\dots, A_n\in\mathbb{N}$ . Cada uno de ellos tiene una descomposición binaria como $A_i = \sum_{j = 0}^k a_{ij}2^j$ donde $k = \max_{i\in[n]}(\lceil \log_2 A_i\rceil)$ es el número máximo de bits necesarios en cualquiera de las descomposiciones binarias. Esto sugiere mirar la matriz $A$ con $(i,j)$ entrada de $a_{ij}$ . Esto es un binario $n\times (k+1)$ matriz en la que el $i$ es la fila (rellenada hasta $k+1$ bits) descomposición binaria de $A_i$ .

Voy a discutir rápidamente cómo interpretar, para $x\in\{0,1\}^k$ , $A_i\&x$ en términos de esto. Si escribimos $A_i = (a_{i0},\dots,a_{ik})$ como su descomposición binaria (y $x = (x_0,\dots, x_k)$ como su descomposición binaria), entonces tenemos que $$\begin{align*} A_i\&x = \sum_{j = 0}^k a_{ij}x_j2^j \end{align*}$$ Es decir, podemos reescribir su AND en términos de algo más cercano a una función lineal-algebraica "estándar". Podemos usar esto para reescribir $F(x)$ como:

$$\begin{align*} F(x) &= \sum_{i = 1}^n A_i \& x\\ &= \sum_{i = 1}^n \sum_{j = 0}^k a_{ij}x_j2^j\\ &= \sum_{j = 0}^k \sum_{i = 1}^n a_{ij}x_j2^j\\ &= \sum_{j = 0}^k x_j2^j \sum_{i = 1}^n a_{ij} \end{align*}$$ Obsérvese en primer lugar que estas sumas están implícitas sobre $\mathbb{Z}$ (no $\mathbb{F}_2$ ). Además, nótese que las cantidades $B_j = 2^j\sum_{i = 1}^n a_{ij}$ son independientes de la elección de $x$ (y se puede precalcular fácilmente calculando $B_j = 2^j\sum_{i = 1}^n A_i\& 2^j$ ).

Esto significa que podemos reescribir $F(x) = \sum_{j = 0}^k x_j B_j = \langle \vec{x}, \vec{B}\rangle$ donde vemos $\vec{x} = (x_0,\dots, x_k)$ y $\vec{B} = (B_0, \dots, B_k)$ como vectores. Su pregunta puede entonces reducirse a dos preguntas:

1. Computar: $$M = \max_{x : |x|_0 = \ell} \langle \vec{x}, \vec{B}\rangle$$
2. Calcule el número de $x$ de peso de martillo exactamente $\ell$ que maximizan esta cantidad

Informática $M$ debería ser fácil. Ordenar $\vec{B}$ en orden descendente, entonces uno debería ser capaz de tomar con avidez el primer $\ell$ entradas de $\vec{B}$ . Su suma será $M$ y no debería ser demasiado difícil demostrar que esta solución es óptima.

El cálculo de la segunda cantidad también debería ser fácil, aprovechando la optimización antes mencionada. Esencialmente, si $(B_{i_0},\dots, B_{i_\ell},\dots, B_{i_k})$ es la forma ordenada de $\vec{B}$ entonces cualquier otra opción de $\vec{x}$ que maximiza $F(x)$ debe "contener los mismos números" $(B_{i_0},\dots, B_{i_\ell})$ . Dejemos que $C = B_{i_\ell}$ sea el número de "corte". Si esto se repite varias veces dentro de $\vec{B} = (B_{i_0},\dots, B_{i_k})$ podemos "intercambiar" instancias de la misma desde después de el $i_{\ell}$ a la entrada de antes de el $i_{\ell}$ para encontrar un nuevo valor $x'$ de peso de martillo $\ell$ que sigue maximizando su función.

Si dejamos que $K$ sea el número de veces que $C$ se produce antes de $i_\ell$ (es decir, el número de valores en $(B_{i_0},\dots, B_{i_\ell})$ que son iguales a $C$ ), y $N$ sea el número total de veces $C$ se produce (es decir, el número de valores en $(B_{i_0},\dots, B_{i_k})$ que son iguales a $C$ ), entonces el número total de $x$ de peso de martillo $\ell$ que maximizan su función se puede ver que es igual a $\binom{N}{K} = \frac{N!}{K!(N-K)!}$ . Esto se debe a que cualquier valor maximizador equivale a elegir todos los $B_i$ que son estrictamente mayores que $C$ y, a continuación, elegir cualquier $K$ (del total $N$ ) que son exactamente iguales a $C$ . Hay $\binom{N}{K}$ posibles opciones, y por lo tanto $\binom{N}{K}$ posibles opciones de $x$ que maximizan la función.

Es decir, un algoritmo es el siguiente:

1. Calcule, para $j\in\{0,\dots,k\}$ los valores $B_j = 2^j\sum_{i = 1}^n A_i\& 2^j$
2. Ordenar la lista $(B_0,\dots, B_k)$
3. Dejemos que $C$ sea el $\ell$ de la lista ordenada, y que $K$ sea el número de veces que $C$ se produce antes de $\ell$ dentro de la lista ordenada, y $N$ sea el número de veces que $C$ se produce dentro de toda la lista $(B_0,\dots, B_k)$ . Entonces la respuesta es $\binom{N}{K} = \frac{N!}{K!(N-K)!}$ .

Como $k = O(\log A_i)$ Esto debería ser bastante eficiente (creo que casi lineal en el tamaño de los bits del $A_i$ y $n$ ).

Técnicamente hay un caso límite del que hay que preocuparse. Si un número suficiente de $B_j$ son cero (en particular, mayores que $(k+1) - \ell$ de ellos), entonces hay un número infinito de asignaciones maximizadoras. Esto se debe a que el algoritmo que describo establece algún bit $x_j$ a uno, aunque $B_j = 0$ . Siempre podemos "cambiar esto" para ajustar cualquier otro bit $x_{j'}$ a uno para $j' > k$ , como $B_{j'}$ es siempre cero. Esto no ocurre si al menos $\ell$ valores de $B_j$ son distintos de cero, lo que parece el "caso típico".