Блог пользователя Theo830

Автор Theo830, история, 4 года назад, По-английски

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

  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

»
4 года назад, # |
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.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

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

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +13 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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

Spoiler