Observe que cada fila le da un punto si voltea todas las columnas que tienen 0 para esa fila O todas las columnas que tienen 1 para la misma fila. Entonces, para cada fila, la combinación de columnas que necesita voltear para obtener un punto es la máscara de bits de esa fila o la máscara de bits negada.
Entonces, si tiene la fila 1 0 0 1 1 0, puede voltear las columnas 2,3,6 (y obtener 1 1 1 1 1 1) o las columnas 1, 4,5 y obtener (0 0 0 0 0 0) obtener un punto para esta fila.
Tenga en cuenta que ninguna máscara de bits puede ser igual a su negación.
Ahora, si decide que una fila en particular es definitivamente parte de la solución, entonces tiene una combinación de columna completa, por lo que solo necesita verificar cuántas otras filas tienen la misma combinación, o su negación como una solución “+1”.
Una cosa que podría hacer es intentar que cada fila itere todas las demás filas y verifique si la combinación de la fila original es compatible (es la misma o la negación de) la combinación de la fila actual. Esto produciría un O (r ^ 2 * c) donde r es el número de filas y c es el número de columnas.
Pero puede hacerlo mejor: dado que para cada combinación de columnas que le da un punto para una fila dada solo puede puntuar en las filas que tienen la misma combinación o la negación allí, en realidad solo necesita contar para cada fila cuántas veces encontrar esa fila o su negación en la matriz. No corre el riesgo de contar una fila dos veces (tanto ella como su negación) ya que una cadena de bits no puede ser igual a su negación.
Entonces como haces esto?
Mantiene un Trie binario de todas las filas y su negación en la matriz. Para construir el trie, necesita dos operaciones de inserción por cada fila, cada una de las cuales toma tiempo O (c). Entonces puedes construir el trie en O (r * c). Ahora, para hacer que el trie sea interesante, en cada nodo hoja (que no tiene descendientes) también mantiene un valor adicional, la cantidad de veces que ocurre. Entonces, si al insertar una cadena binaria como 101101 terminas en un nodo que creaste anteriormente, simplemente incrementas el conteo para ese nodo.
- ¿Cuál es el problema del bandido multi-brazo? ¿Cuáles son algunas de sus implicaciones?
- ¿Qué es el retorno 0 en C?
- Cómo formular matemáticamente para seleccionar los mejores valores de N de una matriz
- ¿Cuáles son algunas aplicaciones del mundo real de punteros en la programación con ejemplos?
- ¿Por qué 0.8 * 3 devuelve 2.4000000000000004 en lugar de 2.4?
Ahora recorre la matriz nuevamente, averiguando para cada fila, cuántas veces ocurre en el Trie (solo al mirarlo y verificando el valor final) y cuántas veces ocurre su negación en el Trie. Esto lleva tiempo O (r * c) ya que hay r filas y cada una tiene el tamaño c. El puntaje máximo será el máximo entre todos estos números. Para cada solución candidata (una fila o su negación), el número de lanzamientos es solo el número de 1 que puede contar.
El tiempo total de ejecución es, por lo tanto, O (r * c) que es lineal en la entrada.
