AND PLUS OR

You can find the statement here.

Let . Then, we just want to find a pair such that .

First, let’s consider a different definition for that makes this problem considerably easier to solve: . Indeed, for this choice of , it suffices to only check adjacent pairs, that is, and . The reason for this is that if , we can decompose as . Similar for . In other words, the set of pairs and form a basis for all possible pairs . Therefore:

1. If all basis elements have value , no combination of them can have value .
2. Otherwise, one of them has value , so we just need to find which one it is.

Now, we can apply a transformation to our original definition of that makes the existence of such a basis more obvious. First, find the (unique) array such that

Then, we see that

Or, if we let , then we must pick a non-empty subset of both and to be in , as well as a potentially empty subset of .

For instance, let . Then, some possible choices for are:

However, is not allowed because has no intersection with .

Let the set of all possible be denoted as . For instance, the valid listed above would be members of . Then, note that we can actually break this into the union of the following smaller sets:

Essentially, we are casing on the last elements of both and . Therefore, the set of configurations with form a basis for all configurations, so we only have to check these for a total complexity of .