Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official. ×

### KyleTheNewbie's blog

By KyleTheNewbie, history, 5 months ago, ,

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
•

 » 5 months ago, # |   +14 Questions are from an ongoing contest.Please discuss after the contest.
 » 5 months ago, # | ← 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.
•  » » 5 months ago, # ^ |   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
•  » » » 5 months ago, # ^ | ← Rev. 2 →   0 Yeah sureSolutions to both these problems are available on my GitHub here. Ask me if you have any doubts :)
•  » » 4 months ago, # ^ |   0 You should use it on problems where a slow solution is feasibleLmao. 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.
•  » » » 4 months ago, # ^ | ← 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. :)
•  » » » » 4 months ago, # ^ | ← 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 leastThat doesn't mean that bitmasking is useless/bad (in general). It depends on what your parameter n is.
•  » » » » » 4 months ago, # ^ |   0 Okay. Thanks :)