Theo830's blog

Need help to find the time complexity!
By Theo830, history, 4 years 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

Comments Comments (7)
| Write comment?
»
4 years 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.

→ Reply
  • »
    »
    4 years 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?

    → Reply
    • »
      »
      »
      4 years 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.

      → Reply
»
4 years ago, # |
  Vote: I like it +4 Vote: I do not like it

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

Spoiler
→ Reply
  • »
    »
    4 years 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).

    → Reply
    • »
      »
      »
      4 years 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.

      → Reply
      • »
        »
        »
        »
        4 years 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.

        → Reply