Author: Lucian Bicsi
Solved by:
First to solve: N/A
Let's start by doing the following pre-computations:
For each string and its proper prefixes, consider the set of its characters and add it to a list
For each query, create a string of length where the r characters are replaced with , the uppercase characters are replaced with , and all the other characters are replaced with .
The problem now becomes the following:
You have a set of numbers of bits (d = 25) and queries (1 \leq q \leq 10^5), consisting of binary patterns with wildcards (containing , , and ). For each of the queries, find a number matching the pattern, or report if no such number exists.
We aim to solve the problem in O(n + 2^{d} \cdot d + q \cdot 2^{d/3}).
Let's notice that if has at most question marks, then we can just brute-force check all possible configurations behind the question marks, in O(2^{d/3}). The more interesting case is when contains many question marks.
In order to solve it, we will build a procedure which will return the number of matches of in (considering that has at least question marks).
Let's suppose contains fewer s than s. In this case, we will compute using inclusion-exclusion on the positions of , as follows:
If does not contain any s, then is the number of subsets of the set of ; for example, if p = 00??0?, then \text{count}(p) = \# \{ x \in S \mid x \t{ OR } 001101_{(2)} = 001101_{(2)} \}. This can be pre-computed for all possible patterns using the popular "sum over subsets" dynamic programming technique;
If contains at least one , then \text{count}(\ldots 1 \ldots) = \text{count}(\ldots ?\ldots) - \text{count}(\ldots 0 \ldots).
This can be recognized as being an inclusion-exclusin over the number of s, and the complexity of the solution is O(2^{o}), where is the number of ones in the pattern.
We can come up with a very similar approach for the case where contains fewer s than s. In this case:
If does not contain any s, then is the number of supersets of the set of s; for example, if p = 11??1?, then \text{count}(p) = \# \{ x \in S \mid x \t{ AND } 110010_{(2)} = 110010_{(2)} \}. This can be pre-computed also using the "sum over subsets (supersets)" technique;
If contains at least one , then \text{count}(\ldots 0 \ldots) = \text{count}(\ldots ? \ldots) - \text{count}(\ldots 1 \ldots).
This, again, ends up being just inclusion-exclusion on the number of s, and the complexity is O(2^z), where is the number of zeros in the pattern.
Choosing the best of the two approaches adaptively yields a complexity of O(2^{\min(o,z)}) = O(2^{d/3}) for .
After having the above procedure, determining an actual solution is easy: just iteratively set some question mark to , and check if the new pattern is still matched (using , of course); if not, change that position to instead. We can do this iteratively until at most question marks remain, where we can transition to brute force.
At first glance such approach might seem that it works in O(2^{d/3} \cdot d) per query (which might sound unpleasantly slow), but after some more thorough examining, the complexity is actually bounded by 2^1 + 2^1 + 2^2 + 2^2 + ... + 2^{d/3} + 2^{d/3} = O(2^{d/3}).