### Theo830's blog

By Theo830, history, 14 months ago,

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?

• +3

 » 14 months ago, # | ← Rev. 3 →   +35 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.
•  » » 14 months ago, # ^ |   +8 Thanks for your response! Can you please explain me how the shift in a bitset works?
•  » » » 14 months ago, # ^ |   +13 Imagine you solve that for N < 64 using a long long to keep the mask. Bitset works in the same way.
 » 14 months ago, # |   +4 An approach better than $dp[i][j]$, but with same complexity. Spoilervector dp(n+1, 0); int m = arr.size(); dp[0] = 1; for(int i = 0; i <= m - 1; i++){ for(int j = n; j >= 0; j--){ if (dp[j]==1) { if(j+arr[i]<=n){ dp[j+arr[i]] = 1; } } } } 
•  » » 14 months ago, # ^ |   0 These approaches are the same (yours just has a little modification that saves memory).
•  » » » 14 months ago, # ^ |   0 I read it in the free version of this book(See page no 72). And now it's paid version is also free.
•  » » » » 14 months ago, # ^ |   0 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.
 » 14 months ago, # |   0 Errichto explained this in his blog Read Errichto's Bitset blog , check problem 2 in problems section and he also explained this in his video Errichto's video