2
$\begingroup$

We are given a set of $n$ bits, call them $a_1$, $a_2$,...,$a_n$. We are also given a set of $m$ sums, where the sums $s_1$, $s_2$,...,$s_k$,...,$s_m$ are given as sums of some of the bits. For example:

$$s_k = a_3 + a_5 + a_{17} + a_{22} + a_{35}$$

There is more structure to the sums, however. The sums are split into $m / \alpha$ groups, where each sum is in only one group. For example, and to make things easier, sums $s_1$, $s_2$,...,$s_{\alpha}$ are in group 1, sums $s_{ \alpha + 1}$,...,$s_{2\alpha}$ are in group 2, and so on. Then we know that each bit will occur exactly once in each group.

So for example, the bit $a_1$ will appear in each group, the bit $a_2$ will appear once in each group, and so on...

QUESTION

How fast can we calculate all of the sums?

MY IDEAS

If we assume that there are $\alpha$ sums in each group, then there are at most $2^\alpha$ combinations of bits. For example, if there are two sums, we know that there are four combinations of bits:

(0) Bits that are not in either sum

(1) Bits that are in sum 1 ($s_1$), but not in sum 2 ($s_2$)

(2) Bits that are not in sum 1 ($s_1$), but are in sum 2 ($s_2$)

(3) Bits that are in both sums.

Thus we need at most $n$ additions to calculate the sums of each of the $m / \alpha$ groups. So our total time is at most $n(m/\alpha)$ additions, since there are $m/\alpha$ groups.


However, I believe that we can do better! I'm guessing that we can also use subtraction and sums from different groups to arrive at a much better algorithm.

$\endgroup$
0
$\begingroup$

I believe that we can do even better than this answer, but perhaps this will help.

We split our list of bits $a_1$, $a_2$, $\dots$, $a_n$ into approximately $n / \beta$ collections (these could also be called groups, but I make the distinction so that we know that these are different from the groups above). Here we set $\beta = \log{(m/(\log{(mn)})}$ In other words, the first collection consists of the first $\beta$ bits $a_1$, $a_2$, $\dots$, $a_{\beta}$. The second collection consists of the second $\beta$ bits $a_{\beta+1}$, $a_{\beta+2}$, $\dots$, $a_{2\beta}$, and so on.

We find all possible sums for each collection, of which there are approximately $2^{\log{(m/(\log{(mn)}))}} = m/(\log{(mn)})$. We then calculate each of these sums exactly. If we're careful, we can calculate each sum in constant time by adding or subtracting one bit from a sum with all other bits the same.

Thus we use roughly $m/(\log{(mn)})$ space to store each solution, times $\log{\log{(mn)}}$ maximum bits per solution, times $n / \log{(mn)}$ different collections.

The running time should be approximately $O \left( \frac{mn \log{ \log{ (mn)}}}{\log{(mn)})^2} \right)$ if I did my calculations right.

This is somewhat faster than the naive approach. Again, I believe that we can do better.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.