PROBLEM LINK:
Author: Sergey Kulik
Tester: Kevin Atienza and Gedi Zheng
Editorialist: Kevin Atienza
PREREQUISITES:
Functional completeness of boolean operators, sqrt decomposition, segment trees/fenwick trees
PROBLEM:
A set of boolean functions is appropriate if it is possible to combine/compose them in any way to produce any boolean function on any number of variables.
Given an array of boolean functions, you have to answer Q queries of two kinds:
- Replace the p th value with a new (given) boolean function.
- Consider the multiset of all functions from the L th to the R th position, and compute how many submultisets of it are appropriate, modulo 10^9+7. Note that in the problem, two functions are considered different if they are in different positions (even if they are essentially the same function).
QUICK EXPLANATION:
According to Wikipedia, a set of boolean connectives is functionally complete (the standard term for “appropriate”) if and only if for each one of the following properties, there is at least one function in the set that violates that property:
- Monotonic
- Affine
- Self-dual
- Truth-preserving
- Falsity-preserving
Each function can be tested in O(|S|) time for each of the properties above, and we can replace each function with a 5-bit mask, where the k th bit is 1 iff the function violates the k th property above. Now, we’ve shown that a subset is functionally complete if and only if the bitwise OR of the masks of all functions is 31 (= 11111_2).
Let’s call the array of masks m = [m_1, \ldots, m_N].
We can construct a segment tree on top of m, where each node contains a length-32 array c. c[i] contains the number of times the mask i appears in the subtree rooted at the node. To implement an update on p, simply decrement c[m_p], update m_p with a new mask and increment c[m_p], for each affected node.
To implement a query in [L,R], compute the 32 values C_0, C_1, \ldots C_{31}, where C_i is the number of times the mask i appears in m[L..R]. This can be done quickly using the segment tree. Afterwards, compute the 32 values S_0, S_1, \ldots S_{31}, where S_i is the sum of all C_j where (i \& j) = 0. The answer to the query is then:
EXPLANATION:
In the problem, we are given an array of boolean functions, and we have to support updates and queries. The “query” part, which asks for the number of functionally complete submultisets of a given subarray, is the toughest, so let’s try to answer the easier question first:
Given a set of boolean functions, is it functionally complete?
(Note that “functionally complete” is just the standard term for “appropriate”)
Now, the problem itself is not that hard (at least compared to the toughest questions in the field of logic). The issue is that you are participating in a short contest, and you probably won’t have enough time to find the correct criteria for a set to be functionally complete (much less prove them). But knowing that this is probably a standard topic and there probably are published results in the internet, your best resort might be to check Wikipedia for hints. And sure enough, there is a neat result in that article which says the following:
A set of boolean connectives is functionally complete if and only if for each one of the following properties, there is at least one function in the set that violates that property:
- Monotonic. Changing the value of any argument from F to T never makes the result of the function change from T to F.
- Affine. Any argument either never affects the result of the function at all, or always affects it.
- Self-dual. If you flip all arguments (i.e. replaces T with F and vice versa), the result of the function is also flipped.
- Truth-preserving. The value of the function is T if each argument has value T.
- Falsity-preserving. The value of the function is F if each argument has value F.
This is really neat: checking whether a set of functions is functionally complete now reduces to checking whether each of the properties above is violated by some function in a set. For a given boolean function, checking each of these properties is pretty straightforward and needs only linear time in the input function. Also, after checking the properties above, we can actually discard the function itself and replace it with a 5-bit number, where the i th bit is 1 if the function violates the i th property above (because these are all we need from it). Let’s call this 5-bit value the function’s property mask. This way, a set of functions is functionally complete if and only if the bitwise-OR of all their property masks is equal to the all-1 s value, or 31 = 11111_2.
Now that we’ve answered that, let’s try to look at how to answer any given query.
Given a set of boolean functions (assuming they are all considered “distinct”), how many subsets of it are functionally complete?
Remember that we can translate this problem into the following (by thinking in terms of property masks):
Given a set of 5-bit numbers (assuming they are all considered “distinct”), how many subsets of it have bitwise OR equal to 31?
This question can be answered by using the inclusion-exclusion principle. Let c_i be the number of times the 5-bit value i appears in the set, for 0 \le i < 32. Also, let S_j be the sum of all c_i for all i having no bits in common with j, i.e. (i \& j) = 0 (note that S_0 is just the sum of all c_i, and S_{31} is just c_0). Then:
- First, include all subsets. There are 2^{S_0} of them.
- By doing so, all subsets whose bitwise OR has at least one bit missing (e.g. 30 = 11110_2, 15 = 01111_2, 27 = 11011_2, …) got included in the count, so we exclude them. There are 2^{S_1} + 2^{S_2} + 2^{S_4} + 2^{S_8} + 2^{S_{16}} of them, or simply \sum_j 2^{S_j} for all j s with exactly one 1 bit.
- But by doing so, all subsets whose bitwise OR has at least two bits missing got excluded in the count multiple times (for instance, subsets with bitwise OR equal to 10110_2 got included in 11111_2 but excluded in 10111_2 and 11110_2), so we include them again to cancel the effect. There are \sum_j 2^{S_j} of them, where j ranges for all values with exactly two 1 bits.
- But by doing so, all subsets whose bitwise OR has at least three bits missing got included again in the count, so we exclude them again to cancel the effect. And so on…
The overall answer is therefore:
How fast does this run? Clearly the $S_j$s can be computed in 32^2 = 4^5 = 1024 steps from the $c_i$s. However, we note that this can also be done in 3^5 = 243 steps, which we’ll leave to the reader to discover how 
(Hint: \sum_{i=0}^5 {5 \choose i}2^i = 3^5).
The only problem now is to compute the $c_i$s themselves in the interval [L,R]. Intuitively, c_i is the number of functions whose property mask is i. This is complicated by the fact that there are updates in the array. But in this case, we can simply construct 32 bit arrays T_0, T_1, \ldots T_{31} that each can perform the following operations:
- Given a position, flip the bit in that position.
- Given an interval, count the number of 1 s in that interval.
Intuitively, T_i represents the occurrences of the 5-bit value i in the original array, i.e. T_i[j] = 1 if and only if the j th function’s property mask is equal to i. In other words, c_i = \sum_{j=L}^R T_i[j]. Clearly, we cannot walk through this interval manually because it might take a lot of time. But notice that the needed operations are exactly what a Fenwick tree can handle efficiently. Thus we can build a Fenwick tree on top of each T_i so each operation runs in O(\log N) time! An alternative method is to construct a single segment tree containing 32 values at each node.
We’ve now described the complete solution to this problem. Preprocessing takes O(32N) = O(N) time using Fenwick trees or segment trees. Each update runs in O(\log N) time and each query runs in O(32\log N + 32^2) = O(\log N). Therefore, the overall algorithm runs in O(N + Q \log N).
Finally, we mention that it also might be possible to solve the problem using sqrt decomposition instead of segment trees/fenwick trees, though with the slower asymptotic running time of O(N + Q \sqrt{N}).
Proving Post’s functional completeness theorem
If you’re curious about the functional completeness theorem above and want to see a proof of it, I’ll refer you to a nice paper about it. However, since proving it is not that hard, I’ll instead give a few hints on how to generate the full proof.
You will need to prove both directions of the theorem. Try proving the forward direction first.
Hints for the forward direction
You want to prove that if a set of boolean connectives is functionally complete, then for each of the five properties above, there is at least one function in the set that violates that property.
Hint: It’s easier to prove the contrapositive: if a set of boolean functions is either ALL monotonic, ALL affine, ALL self-dual, ALL truth-preserving or ALL falsity-preserving, then the set is not functionally complete.
Hint: Try to prove that, for each of the five properties above, any combination/composition of functions satisfying that property results in a function also satisfying that property (For example, combinations of falsity-preserving functions only result in falsity-preserving functions). This means that these functions cannot be combined to create functions without that property.
Hints for the backward direction
Now for the backward direction. You want to prove that, given a set of boolean connectives, if for each of the five properties above there is always a function that violates it, then the set is functionally complete.
Hint: Suppose we have five functions f_i, i = 1, 2, 3, 4, 5, where f_i violates the i th property above. Our goal is to generate all boolean functions using only these five (not necessarily distinct) functions.
Hint: Show the well-known fact that any boolean function in any number of arguments can be created with only AND, OR and NOT functions. In fact, OR is not actually needed because or de Morgan’s law: A \lor B = \neg (\neg A \land \neg B). Therefore, any boolean function can be created with only AND and NOT operators. Our goal then is to recreate AND and NOT using only the five functions above.
Hint: Show that the NOT function can be simulated with f_1, f_4 and f_5.
Hint: Show that the T and F constant functions can be simulated with NOT and f_3.
Hint: Show that with T, F, NOT and f_4, one can create a two-argument boolean function f that has an odd number of T values in its truth table (examples of such functions are AND, OR, NAND, NOR, IMPLIES, etc.).
Hint: Show that with the function f above, together with NOT, can create the function AND.
When you combine all the proofs of the hints above, you get the full theorem
If you want to see the full proof (but please try proving it yourself first before spoiling!), here’s the link (the hints above are patterned after this paper).
Time Complexity:
O(N + Q\log N)