Bitmasks ( Buildup to SoS DP - Pt. 1 )
Bitmasks are pretty cool. For a small-ish superset (<=64 elements), we can describe any subset using binary representation of an integer/long.
For example : Let our superset be [ 10, 12, 14, 15 ] .
Then, a bitmask value of 5 (0101 in binary) would denote the subset [ 12, 15 ]
The basic concept is pretty simple, plenty of tutorials available in the wild, I'd rather write about possible use cases.
Bitmasks are useful in problems where we need to generate all possible subsets of a set.
However, what I am most interested in is their application in DP.
Using a bitmask you can potentially store a whole subset as a DP state using only one int/long as your DP variable.
As for implementing a bitmask, it is really easy. Almost all basic operations on bitmasks are enlisted here
Below is a sample implementation of a bitmask datatype by yours truly. We should keep most of these functions in our codebook next year for sure.
For example : Let our superset be [ 10, 12, 14, 15 ] .
Then, a bitmask value of 5 (0101 in binary) would denote the subset [ 12, 15 ]
The basic concept is pretty simple, plenty of tutorials available in the wild, I'd rather write about possible use cases.
Bitmasks are useful in problems where we need to generate all possible subsets of a set.
However, what I am most interested in is their application in DP.
Using a bitmask you can potentially store a whole subset as a DP state using only one int/long as your DP variable.
As for implementing a bitmask, it is really easy. Almost all basic operations on bitmasks are enlisted here
Below is a sample implementation of a bitmask datatype by yours truly. We should keep most of these functions in our codebook next year for sure.
Comments
Post a Comment