使所有数组元素为零的最少 AND 运算次数

Question

我在一次编程竞赛中遇到了这个问题：

We are given an array consisting of n elements. At each iteration, you can select any two elements a_i and a_j and replace a_i with a_i & a_j. & is the bitwise AND operator. Find the minimum number of AND operations needed to make all array elements zero.

Suppose that there is a solution for the given inputs. What is the optimal solution for this problem?

编辑：我已经为运行花费超过 1 秒的问题添加了我的 DP 解决方案。有什么加快速度的建议吗？

0 < n < 65535

D: maximum number of digits in base 2 (0 < D < 17)

GOAL: 2^D - 1

T[i][X] => minimum number of elements from {n_0, n_1, ..., n_i} that make X zero

T[i][0] = 0

T[0][X>0] = INF

T[i][X] = min( 1 + T[i-1][X & n_i] , T[i-1][X] )

T[n][GOAL] -> min number of AND operations

Answer 1

这在我看来很像 set cover problem。我们需要找到在每个位置都覆盖零的最小子集。找到该子集后，生成的 "absolute" 零可用于将其他元素转换为零。在下面的示例中，子集中的三个元素中的任何一个都可以用作第一个零。

Answer 2

如果问题对于给定的输入有解，您可以执行这些操作：

在 [0,n-1] 之间选择一个索引 i（假设数组索引从零开始）。
对于 0 到 n 之间的每个不是 i 的 j，执行 a_i <- a_i & a_j。此时你保证a_i等于0，否则问题无法解决，因为你对数组中的所有项进行了位和
对于 0 到 n 之间的每个不是 i 的 j，执行 a_j <- a_i & a_j。这对数组中的所有项目执行 0，使它们也为 0。

您在第一个循环中执行了 n-1 次与操作，在第二个循环中执行了 n-1 次，因此总共执行了 2n-2 次与操作。

编辑：

这是假设您无法查看数组中的值。

Answer 3

我的猜测是，您可以通过使 DP table 稀疏来获得所需的加速。我们可以将生成的算法视为在图上进行从 2^D-1 到 0 的广度优先搜索，其中节点为 0..2^D-1，边从 x 到 x&y 其中 y 是数组元素。事实上，由于commutativity/associativity的按位与，我们可以通过要求x&y清除x中的最低位集合来收紧边缘集合。在下面的 Python 代码中，通过使用映射 zero_index 可以稍微有效地实现这一点，但在 C 中我会使用数组（并根据需要用位图或数组替换集合）。

import collections
import random


def min_and(seq):
    lst = list(seq)
    zero_index = collections.defaultdict(lambda: set(lst))
    for x in lst:
        y = x
        while y:
            zero_index[y & ~(y - 1)].discard(x)
            y &= y - 1
    visited = set()
    fringe = set(lst)
    i = 0
    while 0 not in fringe:
        visited.update(fringe)
        fringe = {
            x & y
            for x in fringe for y in zero_index[x & ~(x - 1)]
            if x & y not in visited
        }
        i += 1
    return i + len(lst) - 1


print(min_and(
    random.randrange(2**18) | random.randrange(2**18) | random.randrange(2**18)
    for i in range(100)))

使所有数组元素为零的最少 AND 运算次数

Minimum number of AND operations to make all array elements zero

algorithm

dynamic-programming

greedy

data-structures