Theo830's blog

By Theo830, history, 14 months ago, In English

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?

Capture.png

 
 
 
 
  • Vote: I like it
  • +3
  • Vote: I do not like it

»
14 months ago, # |
Rev. 3   Vote: I like it +35 Vote: I do not like it

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, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Thanks for your response! Can you please explain me how the shift in a bitset works?

    • »
      »
      »
      14 months ago, # ^ |
        Vote: I like it +13 Vote: I do not like it

      Imagine you solve that for N < 64 using a long long to keep the mask. Bitset works in the same way.

»
14 months ago, # |
  Vote: I like it +4 Vote: I do not like it

An approach better than $$$dp[i][j]$$$, but with same complexity.

Spoiler
  • »
    »
    14 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    These approaches are the same (yours just has a little modification that saves memory).

    • »
      »
      »
      14 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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, # |
  Vote: I like it 0 Vote: I do not like it

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