KyleTheNewbie's blog

Need help on bitmasking
By KyleTheNewbie, history, 6 years ago, In English

Any techniques on fast bitmasking? I always hit TLE on these problems: https://www.codechef.com/JULY18B/problems/MGCSET https://www.codechef.com/JULY18B/problems/NMNMX

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

»
6 years ago, # |
  Vote: I like it +14 Vote: I do not like it

Questions are from an ongoing contest.Please discuss after the contest.

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Firstly, these are questions from an ongoing contest. Secondly, Neither of these questions have anything to do with bitmasking.

As a rule, bitmasking is not fast.

You should use it on problems where a slow solution is feasible. Here is a good example.

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

    when the contest is done i want to discuss it with people. coz the only way i know how to solve those is just bitmasking. thank you i'll be back :D

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Yeah sure

      Solutions to both these problems are available on my GitHub here. Ask me if you have any doubts :)

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

    You should use it on problems where a slow solution is feasible

    Lmao. That's not a very good rule. E.g. People who use such rules won't be able to solve bitmask dp problems.

    You know what? Only beginners come up with such rules. There should be no limitation to what you should/can use bitmask on. Problem solving by itself is a creative process after all.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Bitmasking by definition takes O(2^n) complexity at least. Naturally, it would only be useful when the constraints are small.

      Of course, if you have a situation where the complexity of bitmasking is only polynomial for some reason, then you can apply it there as well. But how can you apply an exponential algorithm on a problem with huge constraints ?

      And bitmasking isn't the intended solution for either of the problems presented here. :)

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

        The thing is, we cannot rule out the fact that we can use bitmasking just by looking at the constraints (considering problems in general). Sometimes, after decomposing/massaging the problem, you might discover that a subproblem can be solved using bitmasking (e.g. a yes/no binary search problem where the verification step allows you to use brute force). So it is a bad habit to say that "this algorithm is not suitable" just because of the large constraints of a problem.

        Bitmasking by definition takes O(2^n) complexity at least

        That doesn't mean that bitmasking is useless/bad (in general). It depends on what your parameter n is.

        → Reply