TimberLee's blog

By TimberLee, history, 5 years ago,

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

 » 5 years ago, # |   0 Another Problem using this trick.
 » 5 years ago, # |   +3 COCI 2015/2016 Task UZASTOPNI http://hsin.hr/coci/contest1_tasks.pdf
 » 5 years ago, # | ← Rev. 2 →   +6 Also 685E - Travelling Through the Snow Queen's Kingdom 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.
 » 5 years ago, # |   +14 People are giving tasks but not a single one is describing the idea :(
 » 5 years ago, # | ← 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 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.
•  » » 5 years ago, # ^ |   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.
•  » » » 5 years ago, # ^ |   0 What is knapsack problem !?I saw several problems that called knapsack. Can you explain your problem?
•  » » » » 5 years ago, # ^ |   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.
•  » » 5 years ago, # ^ |   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 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?
•  » » » 5 years ago, # ^ |   +8  template class bitset : private _Base_bitset<_GLIBCXX_BITSET_WORDS(_Nb)> So _Nw = _GLIBCXX_BITSET_WORDS(maxv) = maxv/32 (on a 32-bit system)
•  » » » » 5 years ago, # ^ | ← 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 months ago, # ^ |   0 https://www.spoj.com/problems/TUG/Can this be solved using this?
 » 15 months ago, # |   +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.
•  » » 15 months ago, # ^ |   +6
 » 4 months ago, # |   0 Try this editorial by errichto. Link