Hello Codeforces!↵
↵
This series of videos are focused on explaining dynamic programming by illustrating the application of DP with bitmasking through the use of selected problems from platforms like Codeforces, Codechef, SPOJ, CSES and Atcoder. ↵
↵
After going through this series, you should find yourself confident in solving problems which require the use of dp and bitmasks and also implementing them in a reasonable amount of time.↵
↵
I will also live code and submit the solutions to the problem on the coding platform from where the problem comes.↵
↵
Some Basic elements of Dynamic Programming↵
------------------↵
↵
Some general ideas and my thoughts about DP to help you get started:<br>↵
↵
Part 1: [https://youtu.be/24hk2qW_BCU](https://youtu.be/24hk2qW_BCU)<br>↵
1. What is Divide and Conquer?<br>↵
2. What is Dynamic Programming?<br>↵
3. Types of DP problems.<br>↵
↵
Part 2: [https://youtu.be/yfgKw6BUZUk](https://youtu.be/yfgKw6BUZUk)<br>↵
1. What is a DP-state?<br>↵
2. Characterizing a DP-state.<br>↵
3. What is a recurrence?<br>↵
4. Top Down v/s Bottom Up.<br>↵
↵
Part 3: [https://youtu.be/X-3HklSPx6k](https://youtu.be/X-3HklSPx6k)<br>↵
1. Directed Acyclic Graph(DAG) Representation of DP solution<br>↵
2. Visualizing Top-Down and Bottom-Up.<br>↵
3. Evaluation order for bottom-up codes.<br>↵
4. Analyzing the space and time complexity for a DP solution(derivation).<br>↵
↵
You may also want to checkout these video tutorials:<br>↵
- [Beginner Friendly Series on Dynamic Programming](https://mirror.codeforces.com/blog/entry/80064)<br>↵
- [Dynamic Programming on Trees](https://mirror.codeforces.com/blog/entry/79857)↵
↵
↵
About the series↵
------------------↵
Short video where I talk about the playlist: [https://youtu.be/6sEFap7hIl4](https://youtu.be/6sEFap7hIl4)↵
↵
What is Bitmasking↵
------------------↵
I talk about what is bitmasking before we actually start solving problems that use dp with bitmasking.<br>↵
[https://youtu.be/7FmL-WpTTJ4](https://youtu.be/7FmL-WpTTJ4) ↵
↵
Illustration: Solving the Job Assignment Problem↵
------------------↵
Using a simple problem, I will illustrate how to solve and implement problems which use dp+bitmask concepts.<br>↵
Problem link: [statement](https://docs.google.com/document/d/1zuw8hBXHsiTYTH8u986fQhn8TWfpOk9BQBIRH3lo_W8/edit)<br>↵
Solution: [https://youtu.be/685x-rzOIlY](https://youtu.be/685x-rzOIlY)↵
↵
Illustration: Travelling Salesman Problem↵
------------------↵
Another great problem to illustrate bitmask dp.<br>↵
I will discuss the following:<br>↵
1. What is the TSP?<br>↵
2. Brute force solution.<br>↵
3. Intuition towards an efficient solution.<br>↵
4. Define a DP state, write a recurrence.<br>↵
5. How do I implement this? ANS: bitmasking!<br>↵
6. Analyzing time and space complexities.<br>↵
↵
Link: [https://youtu.be/QukpHtZMAtM](https://youtu.be/QukpHtZMAtM)↵
↵
Codeforces Problem: Div2E↵
------------------↵
I'll discuss a problem named Fish that comes from a Codeforces Divison 2 round.<br>↵
Problem link: [https://mirror.codeforces.com/contest/16/problem/E](https://mirror.codeforces.com/contest/16/problem/E)<br>↵
Solution: [https://youtu.be/d7kvyp6dfz8](https://youtu.be/d7kvyp6dfz8)↵
↵
Codechef long Challenge: Medium↵
------------------↵
The problem comes from Codechef long challenge and is rated MEDIUM by codechef.<br>↵
Problem link: [https://www.codechef.com/problems/TSHIRTS](https://www.codechef.com/problems/TSHIRTS)<br>↵
Solution: [https://youtu.be/Smem2tVQQXU](https://youtu.be/Smem2tVQQXU)↵
↵
CSES: Counting Tilings↵
------------------↵
The problem comes from CSES problemset and was introduced to the problemset in 2021.<br>↵
Problem link: [https://cses.fi/problemset/task/2181](https://cses.fi/problemset/task/2181)<br>↵
Solution: [https://youtu.be/lPLhmuWMRag](https://youtu.be/lPLhmuWMRag)↵
↵
↵
<b>Practice Problems:</b><br>↵
1. https://atcoder.jp/contests/dp/tasks/dp_o <br>↵
2. https://atcoder.jp/contests/dp/tasks/dp_u <br>↵
3. https://www.codechef.com/JAN13/problems/LEALCO <br>↵
4. https://www.spoj.com/problems/HIST2/ <br>↵
5. https://mirror.codeforces.com/problemset/problem/895/C <br>↵
↵
↵
If people find this helpful then I will try and add more problems to this list :)
↵
This series of videos are focused on explaining dynamic programming by illustrating the application of DP with bitmasking through the use of selected problems from platforms like Codeforces, Codechef, SPOJ, CSES and Atcoder. ↵
↵
After going through this series, you should find yourself confident in solving problems which require the use of dp and bitmasks and also implementing them in a reasonable amount of time.↵
↵
I will also live code and submit the solutions to the problem on the coding platform from where the problem comes.↵
↵
Some Basic elements of Dynamic Programming↵
------------------↵
↵
Some general ideas and my thoughts about DP to help you get started:<br>↵
↵
Part 1: [https://youtu.be/24hk2qW_BCU](https://youtu.be/24hk2qW_BCU)<br>↵
1. What is Divide and Conquer?<br>↵
2. What is Dynamic Programming?<br>↵
3. Types of DP problems.<br>↵
↵
Part 2: [https://youtu.be/yfgKw6BUZUk](https://youtu.be/yfgKw6BUZUk)<br>↵
1. What is a DP-state?<br>↵
2. Characterizing a DP-state.<br>↵
3. What is a recurrence?<br>↵
4. Top Down v/s Bottom Up.<br>↵
↵
Part 3: [https://youtu.be/X-3HklSPx6k](https://youtu.be/X-3HklSPx6k)<br>↵
1. Directed Acyclic Graph(DAG) Representation of DP solution<br>↵
2. Visualizing Top-Down and Bottom-Up.<br>↵
3. Evaluation order for bottom-up codes.<br>↵
4. Analyzing the space and time complexity for a DP solution(derivation).<br>↵
↵
You may also want to checkout these video tutorials:<br>↵
- [Beginner Friendly Series on Dynamic Programming](https://mirror.codeforces.com/blog/entry/80064)<br>↵
- [Dynamic Programming on Trees](https://mirror.codeforces.com/blog/entry/79857)↵
↵
↵
About the series↵
------------------↵
Short video where I talk about the playlist: [https://youtu.be/6sEFap7hIl4](https://youtu.be/6sEFap7hIl4)↵
↵
What is Bitmasking↵
------------------↵
I talk about what is bitmasking before we actually start solving problems that use dp with bitmasking.<br>↵
[https://youtu.be/7FmL-WpTTJ4](https://youtu.be/7FmL-WpTTJ4) ↵
↵
Illustration: Solving the Job Assignment Problem↵
------------------↵
Using a simple problem, I will illustrate how to solve and implement problems which use dp+bitmask concepts.<br>↵
Problem link: [statement](https://docs.google.com/document/d/1zuw8hBXHsiTYTH8u986fQhn8TWfpOk9BQBIRH3lo_W8/edit)<br>↵
Solution: [https://youtu.be/685x-rzOIlY](https://youtu.be/685x-rzOIlY)↵
↵
Illustration: Travelling Salesman Problem↵
------------------↵
Another great problem to illustrate bitmask dp.<br>↵
I will discuss the following:<br>↵
1. What is the TSP?<br>↵
2. Brute force solution.<br>↵
3. Intuition towards an efficient solution.<br>↵
4. Define a DP state, write a recurrence.<br>↵
5. How do I implement this? ANS: bitmasking!<br>↵
6. Analyzing time and space complexities.<br>↵
↵
Link: [https://youtu.be/QukpHtZMAtM](https://youtu.be/QukpHtZMAtM)↵
↵
Codeforces Problem: Div2E↵
------------------↵
I'll discuss a problem named Fish that comes from a Codeforces Divison 2 round.<br>↵
Problem link: [https://mirror.codeforces.com/contest/16/problem/E](https://mirror.codeforces.com/contest/16/problem/E)<br>↵
Solution: [https://youtu.be/d7kvyp6dfz8](https://youtu.be/d7kvyp6dfz8)↵
↵
Codechef long Challenge: Medium↵
------------------↵
The problem comes from Codechef long challenge and is rated MEDIUM by codechef.<br>↵
Problem link: [https://www.codechef.com/problems/TSHIRTS](https://www.codechef.com/problems/TSHIRTS)<br>↵
Solution: [https://youtu.be/Smem2tVQQXU](https://youtu.be/Smem2tVQQXU)↵
↵
CSES: Counting Tilings↵
------------------↵
The problem comes from CSES problemset and was introduced to the problemset in 2021.<br>↵
Problem link: [https://cses.fi/problemset/task/2181](https://cses.fi/problemset/task/2181)<br>↵
Solution: [https://youtu.be/lPLhmuWMRag](https://youtu.be/lPLhmuWMRag)↵
↵
↵
<b>Practice Problems:</b><br>↵
1. https://atcoder.jp/contests/dp/tasks/dp_o <br>↵
2. https://atcoder.jp/contests/dp/tasks/dp_u <br>↵
3. https://www.codechef.com/JAN13/problems/LEALCO <br>↵
4. https://www.spoj.com/problems/HIST2/ <br>↵
5. https://mirror.codeforces.com/problemset/problem/895/C <br>↵
↵
↵
If people find this helpful then I will try and add more problems to this list :)
