Bit operations provide an efficient and convenient way to implement dynamic programming algorithms whose states contain subsets of elements, because such states can be stored as integers.
This is a session on competitive programming, for 2nd years IIT(ISM) Dhanbad.
Topic: DP with bitmasks
Session taken by - Chirag Jain
Link to google doc used: https://docs.google.com/document/d/1kRRmdmZlmzplvmasmbYtr_79qc1EfOOJmqm1VHaBZkc/edit#
Pre-requisites: The concept covered in earlier session-
https://www.youtube.com/watch?v=95o1lWeV7fY&feature=youtu.be
You may also go through the following blogs in advance, for better understanding of the topic:
https://www.hackerearth.com/practice/algorithms/dynamic-programming/bit-masking/tutorial/
0:00 Codeforces 1097 B Petr and a combination lock (solving using bitmasks)
12:58 Checking for submasks
19:40 Iterating through all submasks of a mask
44:20 What is DP with bitmasking ?
46:45 solving SPOJ ASSIGN
1:19:05 solving Atcoder DP U - Grouping
1:36:26 practice questions, corrections and some tricks
View the complete CP Level 2 (CodeISM 2023) playlist at:
https://www.youtube.com/playlist?list=PL40a3hTWsqXBFAKwLv-02tsKOLCud6hvf
