daihan's blog

By daihan, history, 8 years ago, In English

Hello codeforces community , can you please suggest me some Bitmask beginner problems ? I am beginner at bitmask . Just Bitmask problems , not Bitmask Dp . Hope someone will suggest me . :)

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

»
8 years ago, # |
  Vote: I like it +5 Vote: I do not like it

It is quiet difficult to find easy problems that require just the use of bitmasks.

Bitmasks are often used to represent states (that's why they are frequently used in DP problems)

First it's important to learn some basic operations with bitmasks

  1. Turn off the ith bit
  2. Turn on the ith bit
  3. Toggle the ith bit (on -> off, off -> on)

Bitmasks can be used to represent sets, if the ith bit is on, then the ith object is included in some set. You can do some set operations.

  1. Get the union of two sets
  2. Get the intersection
  3. Get the difference
  4. Create a set with all the elements.
  5. Print all the subsets from a set

Once you understand how bitmasks work (and how to use them in your programming language), you can solve problems like this one:

Given an array A of at most 20 integers, you must count the number of subsequences from this array which have positive sum

Using bitmasks you can solve this problem in O(n2n), this is not neccessarily the best solution, but it's just an example

I wrote this problem some time ago.

This one doesn't require DP, but it's not that easy though.

You can take a look at Hackerrank too, they have lots of tutorial about some programming techniques, including the use of bitmasks.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you kindly explain how to solve the no. of subsequences with +ve sum ?