使所有数组元素为零的最小AND操作数

Question

我在编程竞赛中遇到了这个问题:

我们给出一个由n个元素组成的数组.在每次迭代中,您可以选择任何两个元素一个_我和一个_Ĵ并更换一个_我有一个_我和一个_Ĵ.&是按位AND运算符.找到使所有数组元素为零所需的最小AND操作数.

假设存在给定输入的解决方案.这个问题的最佳解决方案是什么？

Answer 1

这在我看来就像套装问题.我们需要找到在每个位置都覆盖零的最小子集.一旦找到该子集,生成的"绝对"零可用于将其他元素转换为零.在下面的示例中,子集中的三个元素中的任何一个都可以用作第一个零.

1001
0101<
0011<
1110<
0111

Answer 2

如果问题有给定输入的解决方案,您可以执行以下操作:

1. 选择[0,n-1]之间的索引i(假设数组索引为零).

2. 对于0和n之间不是i的每个j,执行_i < - a _i&a _j.此时,您可以保证a_i等于0,否则问题是不可解决的,因为您按顺序执行了数组中的所有项目.

3. 对于0和n之间不是i的每个j,执行_j < - a _i&a _j.这将对数组中的所有项执行0,使其也为0.

对第一个循环执行和操作n-1次,对第二个循环执行n-1次,因此总共执行2n-2和操作.

编辑:

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

Answer 3

我的猜测是，您可以通过使 DP 表稀疏来获得所需的加速。我们可以将生成的算法视为在节点所在的图上执行从2^D-1到 的广度优先搜索，并且边从到是数组元素。事实上，由于按位 AND 的交换性/结合性，我们可以通过要求清除 中的最低位集来收紧边缘集。在下面的 Python 代码中，通过使用 map 可以在一定程度上有效地实现这一点，但在 CI 中将使用数组（并根据需要用位图或数组替换集合）。00..2^D-1xx&yyx&yxzero_index

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)))