zeddie's blog

How to get good in BitMasks questions?
By zeddie, 4 years ago, In English

I have been on CodeForces for >1y and I have studied various topics from different websites, but BitMasks is that one topic that I never found my way with.

I can solve 1800+ rated questions from Graph and DP, but I am not able to solve 1400+ rated questions from BitMasks.

I have read the theory, of how it works, but still, I am not able to solve its questions, sometimes, I don't even understand the editorial.

Here I am, asking the CodeForces community to guide me, as you guys have always been guiding me.

Thanks ;)

  • Vote: I like it
  • -10
  • Vote: I do not like it

Comments Comments (7)
| Write comment?
»
4 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

The different mask values of Bitmasks are just different subsets of a set. If you have a set = {3, 2, 1} You can represent it's subsets using bitmasks.

000 = {empty set}

001 = {1}

010 = {2}

100 = {3}

110 = {3, 2}

.. ..

111 = {3, 2, 1}

So basically we need values upto 111 to represent all the sets where in each binary number 1 means the element at that position in the original set is present in the current subset (mask).

The mask 111 means all elements of the set are present.

so the mask which represents {3, 2, 1} = 111 = 2*2 + 2*1 + 2*0 = 7 So, if we ran a loop from 0 to 7 we get all the subsets in binary form.

We can use bitmasks as dp states when you need to store a state where the state is a subset of some set. So we can do O(1) lookups when checking the memo array. Had we done the same with boolean map or something it would take O(n) as we would be checking whether this exact map has been seen before.

This is my understanding of bitmasks and I may be wrong in some places so feel free to correct me.

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

    Hey, Thanks for putting all of these. But I am clear with the theory part, I am just not able to find my way with questions. Most of the time, I am not able to solve questions even with editorials too.

    → Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it +1 Vote: I do not like it

This question is too broad to have a concrete answer. You can make it better by providing some problems with the way you approached them.

In general, you can increase your understanding of bitmasks in the following way,

Sets and Subsets:
1. Lets say you are solving a problem for set S
2. Consider the powerset P(S) and the operator ⊆
3. Now, if you build a graph with the objects in P(S) having edge from a -> b if a ⊆ b
4. Now try to solve the problem in the graph you built. If the problem is related to subset and bitmask, you will find it easier to solve it in this graph.
5. It worth nothing to see that this graph forms a category.

Number system
1. Binary number system can be represented with bits
2. Learn little some bit manipulation like << or multiply by 2, >> or integer division by 2 and reading, toggling or writing to nth bit.

Of course in the long run you won't need this kind of analysis to solve the problem. It will come from the intuition.

→ Reply
»
4 years ago, # |
  Vote: I like it +31 Vote: I do not like it
How to get good in bitmask questions
→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

solve questions from this blog. Practicing questions of this blog helped me to improve my bitmask dp & dp(in general also) a lot.

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

I'm essentially copying an old comment I made on Codeforces, but I think a good resource for bitmask DP is this HackerEarth tutorial, I remember it helped me understand the logic behind it. After that, it's just solving problems, some problems that come to mind, from easiest to hardest, are 580D - Kefa and Dishes, this CSES task, 16E - Fish, 678E - Another Sith Tournament.

→ Reply