Блог пользователя TimberLee

Optimising DP using bitset in C++
Автор TimberLee, история, 8 лет назад, По-английски

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 ?

  • Проголосовать: нравится
  • +40
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Another Problem using this trick.

→ Ответить
»
8 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

→ Ответить
»
8 лет назад, # |
← Rev. 2   Проголосовать: нравится +6 Проголосовать: не нравится

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.

→ Ответить
»
8 лет назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

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

→ Ответить
»
8 лет назад, # |
← Rev. 3   Проголосовать: нравится +53 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    → Ответить
    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      What is knapsack problem !?

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

      → Ответить
      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        [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.

        → Ответить
  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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?

    → Ответить
    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится 
        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)

      → Ответить
      • »
        »
        »
        »
        8 лет назад, # ^ |
        ← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

        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?

        → Ответить
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    Can this be solved using this?

    → Ответить
»
5 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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.

→ Ответить