Минимальное количество операций AND для обнуления всех элементов массива

Question

Я сталкивался с этим вопросом в конкурсе по программированию:

Нам дан массив, состоящий из n элементов.На каждой итерации вы можете выбрать любые два элемента a _i и a _j и заменить a _i с a _i & a _j .& является побитовым оператором AND.Найдите минимальное количество операций AND, необходимых для обнуления всех элементов массива.

Предположим, что существует решение для заданных входных данных.Каково оптимальное решение для этой проблемы?

Редактировать: я добавил свое решение DP для задачи, выполнение которой занимает более 1 секунды.Любое предложение по его ускорению?

0

D: максимальное количество цифр в базе 2 (0

ЦЕЛЬ: 2 ^ D - 1

T [i] [X] => минимальное количество элементов из {n_0, n_1, ..., n_i}, которые делают X нулем

T [i] [0] = 0

T [0] [X> 0] = INF

T [i] [X] = мин (1 + T [i-1] [X &n_i], T [i-1] [X])

T [n] [GOAL] -> минимальное количество операций AND

Answer 1

Если у проблемы есть решение для заданного входа, вы можете выполнить следующие операции:

1. Выберите индекс i в диапазоне [0, n-1] (при условии, что индексирование массива равно нулю)на основе).

2. Для каждого j от 0 до n, отличного от i, выполните _i <- a <sub>i & a _J .На этом этапе вам гарантировано, что a_i равно 0, в противном случае проблема не решаема, потому что вы выполнили битовую обработку и для всех элементов в массиве.

3. Для каждого j между 0 и n, который не является iвыполните _j <- a <sub>i & a _j .Это выполняет и для всех элементов в массиве с 0, также делая их равными 0.

Вы выполняете операцию и n-1 раз для первого цикла и n-1 раз для второгоцикл, так что всего 2n-2 и операций.

Edit:

Это предполагает, что вы не можете смотреть на значения в массиве.

Answer 2

Я предполагаю, что вы можете получить необходимое ускорение, сделав свою таблицу DP разреженной.Мы можем представить результирующий алгоритм как выполняющий поиск в ширину от 2^D-1 до 0 на графике, где узлы равны 0..2^D-1, а ребра переходят от x до x&y, где y - этоэлемент массива.Фактически, из-за коммутативности / ассоциативности побитового И, мы можем сжать установленный фронт, потребовав, чтобы x&y очистил младший бит, установленный в x.В приведенном ниже коде Python это достигается несколько эффективно при использовании карты zero_index, но в CI будет использоваться массив (и при необходимости заменять наборы растровыми изображениями или массивами).

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

Answer 3

Мне кажется, что проблема с set cover .Нам нужно найти наименьшее подмножество, которое покрывает нули в каждой позиции.Как только это подмножество найдено, «абсолютный» ноль, который генерируется, может использоваться для преобразования других элементов в ноль.В приведенном ниже примере любой из трех элементов в подмножестве может стать первым нулем.

1001
0101<
0011<
1110<
0111