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 ?

# | User | Rating |
---|---|---|

1 | Benq | 3650 |

2 | Radewoosh | 3648 |

3 | tourist | 3579 |

4 | ecnerwala | 3551 |

5 | Um_nik | 3494 |

6 | Petr | 3452 |

7 | ksun48 | 3432 |

8 | jiangly | 3349 |

9 | maroonrk | 3338 |

10 | Miracle03 | 3314 |

# | User | Contrib. |
---|---|---|

1 | 1-gon | 210 |

2 | awoo | 188 |

3 | Errichto | 186 |

3 | rng_58 | 186 |

5 | SecondThread | 182 |

6 | Um_nik | 176 |

6 | Ashishgup | 176 |

8 | maroonrk | 172 |

9 | antontrygubO_o | 171 |

10 | -is-this-fft- | 169 |

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 ?

↑

↓

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/07/2021 08:14:23 (g1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Another Problem using this trick.

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

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.

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

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:

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

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

My solution.

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.

What is knapsack problem !?

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

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

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 beO(N) only(orO(maxv) from your code). This is the implementation on my system(G++ 4.9.2)And

`_Nw`

is defined in`template<size_t _Nw> struct _Base_bitset`

so basically it makesO(maxv) operations only. The functions`xor`

and`and`

also seem to be implemented similarly. How is this faster than normal looping?So

`_Nw = _GLIBCXX_BITSET_WORDS(maxv) = maxv/32`

(on a 32-bit system)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?https://www.spoj.com/problems/TUG/

Can this be solved using this?

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.

Complete treatise on bitset optimization

Try this editorial by errichto. Link