kartik8800's blog

By kartik8800, history, 3 years ago,

This series of videos are focused on explaining dynamic programming by illustrating the application of DP 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 approaching dynamic programming problems 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

Part 1: https://youtu.be/24hk2qW_BCU
1. What is Divide and Conquer?
2. What is Dynamic Programming?
3. Types of DP problems.

Part 2: https://youtu.be/yfgKw6BUZUk
1. What is a DP-state?
2. Characterizing a DP-state.
3. What is a recurrence?
4. Top Down v/s Bottom Up.

Part 3: https://youtu.be/X-3HklSPx6k
1. Directed Acyclic Graph(DAG) Representation of DP solution
2. Visualizing Top-Down and Bottom-Up.
3. Evaluation order for bottom-up codes.
4. Analyzing the space and time complexity for a DP solution(derivation).

Problem 1: Dice Combinations

Source: CSES
Explanation: https://youtu.be/5gd5jptXWAM

Problem 2: Coin Combinations I

Source: CSES
Explanation: https://youtu.be/5BdAl6gfusg

Problem 3: Coin Combinations II

Source: CSES
Explanation: https://youtu.be/-pXjopzMVrE

Problem 4: Removing Digits

Source: CSES
Explanation: https://youtu.be/32qvB7OP4V8

Problem 5: Grid Paths

Source: CSES
Explanation: https://youtu.be/V64F4wlodUM

Problem 6: Book Shop

Source: CSES
Explanation: https://youtu.be/qpNy2nuSuaI

Problem 7: Array Description

Source: CSES
Explanation: https://youtu.be/d1H5JylYG4I

Problem 8: Edit Distance

Source: CSES
Explanation: https://youtu.be/Ev80c1oIRFg

Problem 9: Rectangle Cutting

Source: CSES
Explanation: https://youtu.be/LdynQjWsO5Q

Problem 10: Two Sets II

Source: CSES
Explanation: https://youtu.be/TOsD3BkIKoQ

Problem 11: Beautiful Array

Source: Codeforces
Explanation: https://youtu.be/IgBLv32QFoQ

Problem 12: Number of Valid Arrays

Source: Coding Interview

Problem 13: Longest Increasing Subsequence O(NlogN)

Source: CSES
Proof and optimization to NlogN: https://youtu.be/66w10xKzbRM
Implementation of the algorithm: https://youtu.be/wqLwv7E1GF0

Problem 14: Projects

Source: CSES
Solution Approach: https://youtu.be/MJn3ogwsUbo
Implementation of the algorithm: https://youtu.be/ISuIwMnSyXc

Problem 15: Beauty of Tree

Source: Kick Start
Explanation: https://youtu.be/ueLRceYVcdE

Problem 16: Catch Some

Source: Kick Start
Explanation: https://youtu.be/ljLIrNKLANE

Problem 17: Vasya and Binary Strings

Source: Codeforces (rated:2400)
Explanation: https://youtu.be/NINZAQFW_AE

Problem 18: Counting Towers

Source: CSES 2021 problem
Explanation: https://youtu.be/pMEYMYTX-r0

I am quite confident that many beginners/intermediates will definitely enjoy watching this series on dynamic programming and it will definitely help in getting better at dynamic programming and problem solving in general. I have tried to teach in a way such that not many prior prerequisites are required to understand the explanations even to the harder problems.

If people find this helpful then I will make sure that this list of problems will keep growing, cheers!

Link for introduction to DP on Trees: https://codeforces.com/blog/entry/79857

UPD: Added 2 more problems from CSES: Projects and Removing digits.
UPD: Added 3 parts on basic elements of DP to get you started.

UPD: I have also started a series on DP with bitmasking(starting from the very basics) and in the future will make a separate blog for both Digit DP series and DP with bitmasking series, till then interested people can check: Dynamic Programming with bitmasking
UPD: added solution to problem Vasya and Binary Strings
UPD: added solution to problem Counting towers from CSES

• +120

| Write comment?
 » 3 years ago, # |   +5 grt work will help many
•  » » 3 years ago, # ^ |   0 Good to know :) will keep adding more.
 » 3 years ago, # | ← Rev. 2 →   +5 I think it would be better for beginners if you add some more problems like lis, max sub-sum etc.by the way great work mate :)
•  » » 3 years ago, # ^ | ← Rev. 2 →   +1 I will definitely consider that, if not the exact same problems, I will definitely be adding variations of those problems which will help clearing up the ideas in a better way.Hope that helps!UPD: Added 2 more problems, one of them being LIS(as suggested by you), where I have discussed both O(N^2) and O(NlogN) approach.
 » 3 years ago, # |   +25 When red coders leave their job to become full-time youtubers vs me if I do the same
 » 3 years ago, # |   0 Auto comment: topic has been updated by kartik8800 (previous revision, new revision, compare).
 » 3 years ago, # |   0 Auto comment: topic has been updated by kartik8800 (previous revision, new revision, compare).
 » 3 years ago, # |   0 Auto comment: topic has been updated by kartik8800 (previous revision, new revision, compare).
 » 3 years ago, # |   0 Please add probability/ expectation value based dp problems. no one covers that :(
•  » » 3 years ago, # ^ |   +1 Will add more! For now try problem 15: beauty of tree.
•  » » 3 years ago, # ^ |   0
•  » » » 3 years ago, # ^ |   +2 Let's be honest, the level of problems he solved in that video grows exponentially rather than polynomially.
•  » » » » 3 years ago, # ^ | ← Rev. 2 →   +1 I don't think that's the case. Perhaps you should first try this amazing wiki on brilliant, to understand the basics: https://brilliant.org/wiki/linearity-of-expectation/
•  » » » » 4 months ago, # ^ |   0 That's what I like, to grow like polynomial
 » 3 years ago, # |   0 I needed a clarification regarding Problem 9. Rectangle Cutting, I know that greedy solution does not give optimal answer, But I cannot come up with a testcase where it fails.By greedy approach I mean, if(a > b) remove a square of (b x b) and proceed;else if(a < b) remove a square of (a x a) and proceed;else : we are done !@[user:karthik8800]( or someone else ) can actually discuss ( elaborate ) , why this approach is wrong .. A counterExample would be of great help!
•  » » 3 years ago, # ^ |   0 Consider 10*9, here is what you will do: 1. Cut 9*9 and remaining portion left is 1*9. 2. For 1*9 minimum cuts needed is 8, so overall 9 cuts. 3. Actual answer for 10*9 is 5.
 » 3 years ago, # |   0 I was just gonna start dp as a complete beginner today and i found this. xD Please try to add different use cases of dp, because noobs like me have no idea where to apply dp. xD
•  » » 3 years ago, # ^ |   +1 I feel you will find this useful :) good luck and enjoy watching!
 » 3 years ago, # |   0 kartik8800, I tried implementing your solution after watching the video, and although almost everything is the same, my solution gets RTE when size of dp array needs to be 10^8. This happened to my "Coins combination 2" solution as well. Can you please look into it and tell me what's causing the RTE although it's almost the same? code#include using namespace std; #define fastIO ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL); #define int long long int #define fi first #define se second #define pub push_back #define pi pair #define all(v) (v).begin(), (v).end() #define rep(i, l, r) for(int i=(int)(l);i<(int)(r);i++) #define repd(i, l, r) for (int i=(int)(l);i>=(int)(r);i--) #define clrg(i, l, r) for(int i=(int)(l);i<(int)(r);i++)vis[i]=0,v[i].clear(); int power(int x, unsigned int y){int res = 1;while (y > 0){ if (y & 1){res = res*x;} y = y>>1;x = x*x;}return res;} int powermod(int x, unsigned int y, int p){int res = 1;x = x % p;while (y > 0){if (y & 1){res = (res*x) % p;}y = y>>1; x = (x*x) % p;}return res;} #define print2d(mat,n,m){for(int i=0;i<(int)(n);i++){for(int j=0;j<(m);j++){cout<>n>>x; vector v(n+1); //int dp[n+3][x+3]; rep(i,1,n+1){ cin>>v[i].fi; } rep(i,1,n+1)cin>>v[i].se; rep(i,1,n+1){ rep(j,1,x+1){ int o1=(i==1?0:dp[i-1][j]); int o2=((j
•  » » 3 years ago, # ^ |   0 The RTE is infact MLE. Try using an int dp array instead of a long long dp array.
•  » » » 3 years ago, # ^ |   0 Worked like magic. :) Thanks for the fast response too.
•  » » » 3 years ago, # ^ |   0 Thanks to your efforts, i gave 658-D "Unmerge" a try, which involved dp. I solved it and submitted, to get 3-4 RTE's. then i again changed long long to int, and it got accepted. My question to you is, this time the size of array was around 10^6 only, which shouldn't be problem? I don't understand when not to use long long arrays. Could you suggest some bounds above which it's not safe to use ll? AC RTE
 » 3 years ago, # |   0 Auto comment: topic has been updated by kartik8800 (previous revision, new revision, compare).
 » 3 years ago, # |   0 Thanks!
 » 3 years ago, # |   0 The link for 'Array Description' problem is wrong. Can you please fix it?
 » 3 years ago, # |   0 Hey kartik8800,I was not able to find dp states or how dp can be applied for the last problem (Catch Some) from kickstart, even though I knew it has to be solved using dp, but I was clueless. Later after watching your video, I realized how we can solve this problem, but still, it took a lot of time to digest what you explained. What should I solve next for practice?
•  » » 3 years ago, # ^ |   0 you can try practicing problems from google kick start.
 » 2 years ago, # |   +1 Auto comment: topic has been updated by kartik8800 (previous revision, new revision, compare).
 » 2 years ago, # |   0 Auto comment: topic has been updated by kartik8800 (previous revision, new revision, compare).
 » 2 years ago, # |   0 I tried to understand Elevator Rides but could not understand. Can you please pick this next kartik8800?https://cses.fi/problemset/task/1653
•  » » 2 years ago, # ^ |   +3 pdf page 113cses book