Today when I was looking at the submissions in problem 1381B - Unmerge I saw 300iq's and Benq's solution. Both submissions(87538626 , 87530540) has a for loop and it does some operations with a bitset in order to find if you can make the sum of some sizes of blocks equal to n. I have done the same solution however I use simple $$$dp[i][j]$$$ = if we can make the sum $$$j$$$ using only the first $$$i$$$ elements. I was wondering what is the time complexity of their dp. Any ideas?
Same as yours but with /32 or /64 (depending on the compiler) constant. The real profit of coding it like that is that code is shorter.
Thanks for your response! Can you please explain me how the shift in a bitset works?
Imagine you solve that for N < 64 using a long long to keep the mask. Bitset works in the same way.
An approach better than $$$dp[i][j]$$$, but with same complexity.
These approaches are the same (yours just has a little modification that saves memory).
I read it in the free version of this book(See page no 72). And now it's paid version is also free.
This is a classic. If you want to know several variations and approaches for the knapsack problem I recommend you this article written by monsoon ; it’s really good.