asifthegreat's blog

By asifthegreat, history, 10 days ago, In English,

Recently, I learned Bitmask DP and used only a variable to see if some block was visited or not. But now I want to do it using std::bitset. Will it be more or less efficient than the first one ? If yes or no, why ? I'm just confused. I think bitset should be fine. and I want to use it because it is easy to use.What's your opinion ? thanks in advance.

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

»
10 days ago, # |
  Vote: I like it -14 Vote: I do not like it

quite obviously, using a primitive data type like long will be more efficient. But the problem is, what if you want to represent a bitmask that has more than 64 bits?

  • »
    »
    10 days ago, # ^ |
      Vote: I like it -6 Vote: I do not like it

    :( . Yah . I think it is not possible using bitset :'(

  • »
    »
    10 days ago, # ^ |
    Rev. 2   Vote: I like it +29 Vote: I do not like it

    quite obviously, using a primitive data type like long will be more efficient.

    Actually gcc's standard lib implementation is specialised for short bitset and uses one long instead of array of longs, so they may be close to the same (but of course, it may still be not true, I have not measured that)

»
10 days ago, # |
  Vote: I like it +3 Vote: I do not like it

I think int is easier to use for bitmask dp because it is easier to store and loop through all possible states. The main use for bitset I have seen is when you have an O(n2) dp solution and are looking for an extra speed boost to squeeze it in the time limit. Definitely a cool trick that makes problem setters sad/apologetic when it works.