Minimum number of AND operations to make all array elements zero

M

3

6

I came across this question in a programming contest:

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?

Edit: I've added my DP solution for the problem which takes more than 1 second to run. Any suggestion for speeding it up?

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

Mephitis answered 25/2, 2019 at 12:58 Comment(11)

"Suppose that there is a solution. What is the optimal solution for this problem?" A solution does not materialize just because you suppose it exists :) Anyways, what did you try? – Lawlor 25/2, 2019 at 13:2

What are your thoughts? Any leads? You tagged the question with 'dynamic programming' so it sounds like you have an idea. – Remorseless 25/2, 2019 at 13:3

That part of the question is to be understood within the context of the problem. For instance, for the array {1,1} there is no solution because 1 & 1 = 1, so the array cannot be cleared with the described operations. – Soule 25/2, 2019 at 13:4

There seems to be missing information. Without knowing the values in the array you can't say whether or not and'ing two elements will yield zero. – Williemaewillies 25/2, 2019 at 13:4

@גלעדברקן Yes, I am aware of that part of the question. I just wanted to state that I believe this comment meant to restrict the problem to instances which can be solved. I was under the impression that BlackBear understood that statement in an informal way, like "my question has an answer". – Soule 25/2, 2019 at 13:16

@Lawlor It is a question I saw in a programming contest. The problem statement says that there is a solution for the given inputs. The only solution came to my mind was BruteForce!! – Mephitis 25/2, 2019 at 13:19

Is this programming contest still on going? Please sent a link to it. – Pyemia 25/2, 2019 at 13:43

@500-InternalServerError: you know that the and of all values is certainly zero. – Bedlamite 25/2, 2019 at 16:7

@Pyemia No, it is not. – Mephitis 25/2, 2019 at 20:7

What's the constraint on D? – Reinforcement 28/4, 2019 at 0:20

@DavidEisentat it's smaller than 18 – Mephitis 28/4, 2019 at 4:14

R

3

My guess is that you can get the needed speedup by making your DP table sparse. We can think of the resulting algorithm as doing a breadth-first search from 2^D-1 to 0 on a graph where the nodes are 0..2^D-1 and the edges go from x to x&y where y is an array element. In fact, due to the commutativity/associativity of bitwise AND, we can tighten the edge set by requiring that x&y clear the lowest bit set in x. In the Python code below, this is achieved somewhat efficiently by using a map zero_index, but in C I would use an array (and replace the sets with bitmaps or arrays as appropriate).

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

Reinforcement answered 28/4, 2019 at 22:48 Comment(6)

Thanks for the solution. It works. Can you explain more about y & ~(y - 1) part and tightening the edges set? Why clear the lowest bit? – Mephitis 29/4, 2019 at 7:17

@Mephitis y & ~(y - 1) is an idiom that extracts the lowest set bit. We know that there must be a number with this bit clear in the bitwise AND, so by forcing it to be the first step in the graph, we reduce the number of intermediate states that we have to consider. – Reinforcement 29/4, 2019 at 11:46

I gave the bounty to another user by mistake. I am sorry. – Mephitis 30/4, 2019 at 5:38

@Mephitis Eh, I have enough rep. – Reinforcement 30/4, 2019 at 11:59

I measured the runtime of the algorithm. It's still not quite as fast as I wanted it to be. However, the data structures employed by your code are quite optimal. Any suggestion for a faster implementation? – Mephitis 30/4, 2019 at 12:34

@Mephitis Working in C++, I'd make zero_index a vector of vectors and use an intrinsic to find the index of the first zero (or find the first one in ~x) for look-ups. I'd make visited a bitmap, and fringe a vector, but update visited eagerly to prevent duplicates in fringe. – Reinforcement 30/4, 2019 at 12:42

V

8

This seems to me like the set cover problem. We need to find the smallest subset that covers zeros in every position. Once that subset is found, the "absolute" zero that's generated can be used to convert other elements to zero. In the example below, any of the three elements in the subset can be used to become the first zero.

Varix answered 25/2, 2019 at 13:44 Comment(12)

Nice solution. What about optimality proof? – Lambent 25/2, 2019 at 16:37

@AsafRosemarin do you mean optimality of set cover in finding an answer, or optimality of the smallest subset covering all zeros expressing the minimum number of moves needed? I would hope the latter is more-or-less self evident. – Scyphozoan 25/2, 2019 at 16:41

The second option – Lambent 25/2, 2019 at 16:42

@AsafRosemarin seems self evident. If we don't have all zero positions covered in a subset, how can we make any "absolute" zero from that subset? – Scyphozoan 25/2, 2019 at 16:43

I didn't mean that such a subset may not exist, what I meant by optimality proof is to prove that this strategy (finding the minimal subset cover, creating an absolute zero, using it to zero the whole array) is optimal in amount of AND operations. – Lambent 25/2, 2019 at 16:47

After thinking about it for a moment, it is pretty trivial to prove indeed. I like your solution :) – Lambent 25/2, 2019 at 16:50

Actually in the set cover problem the n is the size of the universe - here it means the size of the number in bits or log 2 (largest number) which is usually a constant in programming contest. So you are looking for another problem where k - number of sets is actually the n, and n is const. (Probably same solution, just FYI) – Pyemia 25/2, 2019 at 17:37

@גלעדברקן How should we find the smallest subset that covers zeros in every position? – Mephitis 25/2, 2019 at 20:17

@Mephitis set cover is a known, researched problem. I would look for literature addressing the binary circumstance. But perhaps Gregory has a correct interpretation of the question? Are you sure we are permitted to examine the array elements? – Scyphozoan 25/2, 2019 at 22:37

@Mephitis In the real world, use an integer program solver. In a contest, maybe branch and bound would be good enough. Implementing dual simplex would admittedly take a while though. – Reinforcement 26/2, 2019 at 0:22

@גלעדברקן I edited my question. Can you take a look at it? – Mephitis 8/4, 2019 at 12:40

@DavidEisentat Can you take a look at my edited question? – Mephitis 10/4, 2019 at 21:26

M

4

If the problem has a solution for a given input, you can perform these operations:

Choose an index i between [0,n-1](assuming array indexing is zero based).
For every j between 0 and n that is not i, perform a_i <- a_i & a_j. At this point you are guaranteed a_i equals 0, otherwise the problem is unsolveable because you performed bitwise and on all items in the array.
For every j between 0 and n that is not i, perform a_j <- a_i & a_j. This performs and on all items in the array with 0, making them 0 also.

You perform the and operation n-1 times for the first loop and n-1 times for the second loop, so in total 2n-2 and operations.

Edit:

This is assuming you cannot look at the values in the array.

Madai answered 25/2, 2019 at 14:22 Comment(3)

"Find the minimum number of AND operations needed to make all array elements zero." suggests to me that the return value needs to be an integer. Your solution isn't minimal (and doesn't count how many ANDs even had an effect). If you just need to zero an array, there are far easier ways that bitwise combining elements. – Atalaya 25/2, 2019 at 14:30

Your solution gives the maximum number of needed AND operations. – Mephitis 25/2, 2019 at 20:8

(I added a space to your answer just to be able to upvote it. I had downvoted before but depending on how we interpret the question, this could be a correct answer.) – Scyphozoan 25/2, 2019 at 21:47

R

3

My guess is that you can get the needed speedup by making your DP table sparse. We can think of the resulting algorithm as doing a breadth-first search from 2^D-1 to 0 on a graph where the nodes are 0..2^D-1 and the edges go from x to x&y where y is an array element. In fact, due to the commutativity/associativity of bitwise AND, we can tighten the edge set by requiring that x&y clear the lowest bit set in x. In the Python code below, this is achieved somewhat efficiently by using a map zero_index, but in C I would use an array (and replace the sets with bitmaps or arrays as appropriate).

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