TimberLee's blog

Optimising DP using bitset in C++
By TimberLee, history, 8 years ago, In English

I recently read somewhere that some DP solutions like knapsack can be optimised and the overall complexity can be reduced by a factor of 32 using std::bitset in C++.

Can someone explain this optimisation and the kinds of DP on which this works ?

  • Vote: I like it
  • +40
  • Vote: I do not like it

Comments Comments (14)
| Write comment?
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Another Problem using this trick.

→ Reply
»
8 years ago, # |
  Vote: I like it +3 Vote: I do not like it

COCI 2015/2016 Task UZASTOPNI http://hsin.hr/coci/contest1_tasks.pdf

→ Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it +6 Vote: I do not like it

Also 685E - Путешествие по царству Снежной королевы in a recent CF round.
Basically, the idea is that you can use bit-wise operations on bitset to determine 32 times more values in one run compared to bool or int.
I think it can work on any DP where the output is boolean like can we reach this state or not.

→ Reply
»
8 years ago, # |
  Vote: I like it +14 Vote: I do not like it

People are giving tasks but not a single one is describing the idea :(

→ Reply
»
8 years ago, # |
← Rev. 3   Vote: I like it +53 Vote: I do not like it

Hi !

Problem is: we have n numbers, calculate how many distinct numbers we can form by sum some of these numbers.

For example if we have set {17, 23, 40}, we can form {0, 17, 23, 40, 57, 63, 80}.

Dp solution is obvious:

dp[0] = 1;
for(int i = 0; i < n; i++)
    for(int j = maxv - 1; j >= a[i]; j--)  // maxv is some number bigger than sum of a[i]'s
        dp[j] |= dp[ j - a[i] ];
cout << count(dp, dp + maxv, 1) << '\n';

Now how to optimize it? bitset can store bits and do operations 32 times faster like this:

bitset<maxv> dp;
dp.set(0);
for(int i = 0; i < n; i++)
    dp |= dp << a[i];
cout << dp.count() << '\n';

Good problem (and hot!) to solve: SnackDown 2016 Online elimination round » Robot Walk.

My solution.

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

    Can you tell how to solve knapsack using it? we can do the same thing with weights but how to store the value we are getting from that particular weight.

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

      What is knapsack problem !?

      I saw several problems that called knapsack. Can you explain your problem?

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

        [user:Arpa]The knapsack problem or rucksack problem is a problem in combinatorial optimization: Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible.

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

    Can you explain why exactly using bitset is O(N / 32). I tried looking it up but couldn't find any exact reasons.

    I tried to read the library implementation of bitset(from usr/include/bitset) and it appears to be O(N) only(or O(maxv) from your code). This is the implementation on my system(G++ 4.9.2)

    void
      _M_do_or(const _Base_bitset<_Nw>& __x)
      {
	for (size_t __i = 0; __i < _Nw; __i++)
	  _M_w[__i] |= __x._M_w[__i];
      }

    And _Nw is defined in template<size_t _Nw> struct _Base_bitset so basically it makes O(maxv) operations only. The functions xor and and also seem to be implemented similarly. How is this faster than normal looping?

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it 
        template<size_t _Nb>
    class bitset
    : private _Base_bitset<_GLIBCXX_BITSET_WORDS(_Nb)>

      So _Nw = _GLIBCXX_BITSET_WORDS(maxv) = maxv/32 (on a 32-bit system)

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
        ← Rev. 3   Vote: I like it 0 Vote: I do not like it

        Ah nice I seemed to mix up the definitions of _Base_bitset and bitset. So now we basically have an N digit binary number split into groups of size 32 and dealt with individually. Is that understanding right?

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

    https://www.spoj.com/problems/TUG/

    Can this be solved using this?

    → Reply
»
5 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Could someone show me some tutorials or blogs that about bitset optimization? Or you guys can give me some basic understanding and I will try to search for things.

Thanks in advanced <3 <3.

→ Reply