report VI VI EN
Register | Login
  • HOME
  • PROBLEMSET
  • ROADMAP
  • COMPETITION
  • TOPIC
  • RANKING
  • GUIDE
  • MASHUP
  • ABOUT
  • CONTACT
Module Bitmask DP

Bitmask DP

**Frequency: 5/10** Use a bitmask to represent DP state. One helpful clue to recognize problems suitable for this approach is to look for suspiciously small problem constraints.

Resources

- [USACO: Bitmask DP](https://usaco.guide/gold/dp-bitmasks?lang=cpp)

Problems

Binary board 442 / 455 1100
Travelling Salesman Problem 2 377 / 439 1200
Brewing potion 5 308 / 323 1200
Subsequences counting 252 / 292 1400
Wooden house 204 / 212 1400
Xiangqi 84 / 94 1400
Packing 179 / 199 1500
Permutation counting 126 / 140 1500
Counting tilings 129 / 142 1600
Superstring 70 / 96 1600
Custom keyboard 114 / 124 1800
Mushroom harvesting III 27 / 35 2300

Graph

  • Shortest path
  • 0-1 BFS / Dial's algorithm
  • Multisource BFS / Dijkstra
  • DAG / Topological sort

Data structure

  • Introduction to Segment Tree and Binary Indexed Tree
  • Sparse table
  • Monotonic queue

Tree

  • Lowest common ancestor (LCA)
  • Euler tour

Dynamic Programming

  • Bitmask DP
  • Exchange labels DP
  • Game DP

Math

  • Introduction to combinatorics
  • Inclusion-exclusion principle