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

# | User | Rating |
---|---|---|

1 | tourist | 3509 |

2 | OO0OOO00O0OOO0O0…O | 3327 |

3 | Um_nik | 3297 |

4 | Syloviaely | 3274 |

5 | LHiC | 3216 |

6 | Petr | 3161 |

7 | Benq | 3130 |

8 | ko_osaga | 3124 |

9 | Swistakk | 3089 |

10 | dotorya | 3060 |

# | User | Contrib. |
---|---|---|

1 | Radewoosh | 185 |

2 | rng_58 | 161 |

3 | tourist | 158 |

4 | Petr | 152 |

5 | Swistakk | 150 |

5 | Vovuh | 150 |

7 | csacademy | 147 |

8 | PikMike | 146 |

9 | Errichto | 145 |

9 | Um_nik | 145 |

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

↑

↓

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Sep/20/2018 14:47:47 (d1).

Desktop version, switch to mobile version.

User lists

Name |
---|

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

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.

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

Yeah sure

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

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.

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

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

nis.Okay. Thanks :)