usernameson's blog

By usernameson, history, 2 years ago, In English

Overview

Assume you are doing bitmask dp where each mask starts with a value and for every mask you want to add this value to all its submasks.

Example Type problem

You have an array $$$a$$$ and for each number $$$x$$$ in $$$[1,10^{6}]$$$ you want to know how many $$$a_{i}$$$ have the property $$$a_{i}$$$ & $$$x = x$$$.

Standard approach

You can use the standard submask iteration to do it in $$$O(3^n)$$$. For the example type problem the initial value for each $$$x$$$ is the number of times it appears in the array and these counts get added to all submasks.

Slight speed up

You can speed this up slightly by using a lazy prop style technique. You iterate through all masks in decreasing order and remove a bit in the original mask. This becomes your new mask call it mask2. You then add the value of mask to the value of mask2. Next you iterate through all submasks of mask2 and add the value to the submask with bit removed added back.

Example implementation

Code
Problem Application
  • Vote: I like it
  • +8
  • Vote: I do not like it

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by usernameson (previous revision, new revision, compare).

»
2 years ago, # |
  Vote: I like it +24 Vote: I do not like it

The actual standard approach for this is a simple $$$O(k \cdot 2^k)$$$ loop on $$$k$$$-bit numbers. If you view the bitmasks $$$[0 \ldots 2^k - 1]$$$ as a $$$k$$$-dimensional array with length 2 in each dimension, this amounts to taking suffix sums along each axis in turn. Alternatively, you can view this process as a DP as is described in this blog. Or, you can view it as a factorization of the linear operator that performs this transform, as is described in this blog.

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks. That's a much a better approach. I need to read those blogs.

»
2 years ago, # |
  Vote: I like it +1 Vote: I do not like it