PROBLEM LINK:Author: Sergey Kulik 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:
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:
Each function can be tested in $O(S)$ time for each of the properties above, and we can replace each function with a 5bit 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: $$\sum_{i=0}^{31} (1)^{\text{bitcount(i)}}2^{S_i}$$ 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:
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 bitwiseOR 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 inclusionexclusion 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:
The overall answer is therefore: $$\sum_{j=0}^{31} (1)^{\text{bitcount}(j)} 2^{S_j}$$ 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:
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 theoremIf 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 selfdual, ALL truthpreserving or ALL falsitypreserving, 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 falsitypreserving functions only result in falsitypreserving 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 wellknown 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 twoargument 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)$ AUTHOR'S AND TESTER'S SOLUTIONS:
This question is marked "community wiki".
asked 12 Jun '15, 05:47
