AND Reconstruction#13009

AND Reconstruction (Editorial)

Author:

Pavle Martinović

Solved by:

First to solve:

Sigma-=-1

First, it’s easy to notice that if is a valid solution, then so is k-1 because the AND of an interval of range can be obtained as an AND of two ANDs of intervals of length k-1 contained inside it. Also k=1 is always a solution since that’s just the array. Because of this, and because all bits are independent, we can solve all bits independently and taking the minimum to obtain the full solution. So we can solve the problem for just bit and every element is either or .

The first insight is that if there are three consecutive zeros, then the answer is always . The reason for this is because the middle zero can be replaced with a one and not change any AND of consecutive elements for k > 2, which obviously prevents reconstruction.

Now if there are no three consecutive zeros, the blocks of zeros are either of length or , while between them, there are some blocks of ones. Let be the shortest block of ones. We claim this is the solution. If is larger than , then the shortest block of ones can be replaced with all zeros and will not change any AND of a range of length , so construction is impossible. On the other hand, if is equal to , then any block of ones will be "identified" by a block of size , and moving one-by-one we can find the first zero to the left and to the right of each block. However, since there are at most zeros in a block of zeros, this allows us to identify all zeros! This means that this uniquely determines the array.