Блог пользователя KyleTheNewbie

Need help on bitmasking
Автор KyleTheNewbie, история, 6 лет назад, По-английски

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

  • Проголосовать: нравится
  • -17
  • Проголосовать: не нравится

»
6 лет назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

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

→ Ответить
»
6 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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

    → Ответить
  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    → Ответить
    • »
      »
      »
      6 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      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. :)

      → Ответить
      • »
        »
        »
        »
        6 лет назад, # ^ |
        ← Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

        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.

        → Ответить