You are literally a godsend priyansh. Its due to you i have become a specialist in codeforces and DP makes sense to me. Thank a lot for everything you have been doing for the community. i hope someday i become good enough to become a mentor at TLE and meet you.
The trick is always to focus on the meaning of the state and you will find it relatively easier to follow the video and also better understand your own implementation.
can some one please help me why is this giving tle Here dp[i][j] = total ways to construct i using first j element of the choice(v) array void send(){ int n,x; cin>>n>>x; vectorv(n); for(int i=1;i>v[i]; vectordp(x+1,vector(n+1)); for(int i=1;i
Day05 of DP series :- In whole Video what i like most is the explnation of the flow of Loops..... Doubt is why we use pick - not pick previous code ke jaise iterate karege aur set me store karege to nhi chalega kya ? and sir give me small test case for dry Run.... Thanks For Better Explnation fear kam ho raha ki without recursion i can write iterative code 😊😊😊😊😊😊
And Also in the case of if we have don't allow to use same number again so we will make our transition like that dp[i+1][k] for skipping dp[i][k] dp[i+1][k-ci] for picking am i right sir ?
Bhaiya all the problems i solved of cses except 4 last problem and first 12 problem at atcoder as you said in the video which is what topic should be done in order to become the expert , i am not comfortable and lil fear of story form of problem , what should i do ?
Can u explain also explain about solving using push dp. It is easy to think and there is less bothering about the indices. But it fails in some cases. Can u explain it also???
@@TLE_Eliminators No no, I am just requesting to please explain about the push dp approach also if possible as it is easy to think. But it has some order of evaluation concern. Which is difficult to understand. It would be helpful if Priyansh bhaiya can explain a little bit about that also.
You don't need that push dp concept to solve any of these problems. There is a problem (money sums) which is related to what you're talking about and Priyansh is going to cover that so you might get an idea of that in that video.
The constraints on CSES are pretty tight so recursive codes usually give a TLE. We suggest coding these problems iteratively and also working on building the iterative dp mindset.
dp[0][x] = make sum = x from 0th coin to n-1th coin , apply this to our state definition dp[i][j] = make sum = j from ith coin till n-1st coin (0 based indexing of coins array)
@@lt0019 I checked online the reason is because of Caches getting misses in columnMajor Array, if you'll change it with dp[sum][n] => More no. of bytes are can be read sequentially.
after watching the video multiple times(hours) im still not understanding why dp[i][sum] = dp[i+1][sum] + dp[i][sum-Ci] and how the picked and skipped is working ...anybody please tell me.......
Then see there are two choices now, 1. You decide to skip coin i, in this case you will have to make the same sum with coins from i + 1 to n, hence dp[i+1][sum] 2. You decide to pick coin i, in this case you can again pick up coin on the next steps but your sum reduces by the value of the coin, hence dp[i][sum- ci] Clearly, if there are 2 possible ways, you would just add up both of them to find your answer for dp[i][sum]. Does this help?
can some one please help me why is this giving tle Here dp[i][j] = total ways to construct i using first j element of the choice(v) array void send(){ int n,x; cin>>n>>x; vectorv(n); for(int i=1;i>v[i]; vectordp(x+1,vector(n+1)); for(int i=1;i
i think its not about the time complexity but more about space complexity. Your solution's space complexity is O(n*x) , while the accepted space complexity is O(x)
@@SlapB0X actually the solution is getting submitted when the dp[x][n] is changed to dp[n][x] and the the loops are also reversed. whereas with the upper solution i t is giving tle
@@nishanttyagi3665it has something to do with the way memory works at lower level. If you have to make an array of size SxL make it as array[S][L] instead of array[L][S], where S is the smaller and L is the larger dimension respectively. It is a bit faster.
Wishing you all a very Happy Diwali. Hopefully with this series you will be able to eliminate your fear of DP by the end of November.
Happy Diwali to you 🎇🎇🎇. P.S. : There's a great article for this problem on USACO
A Very Happy Diwali Bbhaiya. Thank you very much this wonderful series I am able to understand everything.💚
yes
You are literally a godsend priyansh. Its due to you i have become a specialist in codeforces and DP makes sense to me. Thank a lot for everything you have been doing for the community. i hope someday i become good enough to become a mentor at TLE and meet you.
After watching 3rd time this video, I understood dp[i][k]. why happend this one could not understand before, now it's clear to me. Thanks a lot.
The trick is always to focus on the meaning of the state and you will find it relatively easier to follow the video and also better understand your own implementation.
can some one please help me why is this giving tle
Here dp[i][j] = total ways to construct i using first j element of the choice(v) array
void send(){
int n,x;
cin>>n>>x;
vectorv(n);
for(int i=1;i>v[i];
vectordp(x+1,vector(n+1));
for(int i=1;i
Just amazing man!!
thanks bhaiya for the wonderfull series!
Extremely good and simple explanation, would love to reach the end of this playlist....
Just Amazing ! really learning and enjoying this series bhaiya. Thanks a ton for this level of content!!
Understood bhaiya❤❤
best lecture series on DP, bhaiya I think you should add Space optimisation
The very next lecture is on that💪😜
thank you sir🤗
Is there any recursive solution possible for this problem? getting tle for this constraints.
Day05 of DP series :- In whole Video what i like most is the explnation of the flow of Loops..... Doubt is why we use pick - not pick previous code ke jaise iterate karege aur set me store karege to nhi chalega kya ? and sir give me small test case for dry Run.... Thanks For Better Explnation fear kam ho raha ki without recursion i can write iterative code 😊😊😊😊😊😊
And Also in the case of if we have don't allow to use same number again so we will make our transition like that
dp[i+1][k] for skipping
dp[i][k]
dp[i+1][k-ci] for picking
am i right sir ?
Understood
understood.
understood
Bhaiya all the problems i solved of cses except 4 last problem and first 12 problem at atcoder as you said in the video which is what topic should be done in order to become the expert , i am not comfortable and lil fear of story form of problem , what should i do ?
Can we watch this series , if I am a complete beginner to DP?
I'll start learning DP soon after my exams.
Absolutely
Can u explain also explain about solving using push dp. It is easy to think and there is less bothering about the indices. But it fails in some cases. Can u explain it also???
Can you please elaborate a bit. What is the meaning of your state in the push dp context.
@@TLE_Eliminators No no, I am just requesting to please explain about the push dp approach also if possible as it is easy to think. But it has some order of evaluation concern. Which is difficult to understand. It would be helpful if Priyansh bhaiya can explain a little bit about that also.
You don't need that push dp concept to solve any of these problems. There is a problem (money sums) which is related to what you're talking about and Priyansh is going to cover that so you might get an idea of that in that video.
understood
Why recursion+memoized solution gives TLE for max constraints?
The constraints on CSES are pretty tight so recursive codes usually give a TLE. We suggest coding these problems iteratively and also working on building the iterative dp mindset.
@@TLE_Eliminators okk will do iteratively. Thanks for replying
background music name please
#day5
why are we returning dp[0][x]??
dp[0][x] = make sum = x from 0th coin to n-1th coin , apply this to our state definition
dp[i][j] = make sum = j from ith coin till n-1st coin (0 based indexing of coins array)
O(n^2) is giving TLE
May be you'll be doing dp[sum][n] instead do dp[n][sum] => This improves the time complexity by a lot.
@@pushpendrahpx but why?
@@lt0019 I checked online the reason is because of Caches getting misses in columnMajor Array, if you'll change it with dp[sum][n] => More no. of bytes are can be read sequentially.
yehi same code mai kab se recursive se kr raha hu..... sahi kyu nahi aa raha.. or i'm damn sure mera code sahi hai..!!
bhai woh cses pe recursive code submit nhi hota pata nhi kyu
@@tajuddinmalnas1903 bro i find out.. (Just not don't use long long in place of int..)
@@Negijicoder thanks buddy
Difficult to understand, need some more effective explanation
tabulation?
What do you mean?
@@TLE_Eliminators i meant method we are using here is tabulation and not memoization right?
after watching the video multiple times(hours) im still not understanding why dp[i][sum] = dp[i+1][sum] + dp[i][sum-Ci] and how the picked and skipped is working ...anybody please tell me.......
Let's start by understanding what is the meaning of the state. What do you think is meant by dp[i][sum]?
@@TLE_Eliminators no of ways to make sum by using i to n coins
Then see there are two choices now,
1. You decide to skip coin i, in this case you will have to make the same sum with coins from i + 1 to n, hence dp[i+1][sum]
2. You decide to pick coin i, in this case you can again pick up coin on the next steps but your sum reduces by the value of the coin, hence dp[i][sum- ci]
Clearly, if there are 2 possible ways, you would just add up both of them to find your answer for dp[i][sum].
Does this help?
@@TLE_Eliminators yes great explanation bhaiya
can some one please help me why is this giving tle
Here dp[i][j] = total ways to construct i using first j element of the choice(v) array
void send(){
int n,x;
cin>>n>>x;
vectorv(n);
for(int i=1;i>v[i];
vectordp(x+1,vector(n+1));
for(int i=1;i
i think its not about the time complexity but more about space complexity.
Your solution's space complexity is O(n*x) , while the accepted space complexity is O(x)
@@SlapB0X actually the solution is getting submitted when the dp[x][n] is changed to dp[n][x] and the the loops are also reversed. whereas with the upper solution i t is giving tle
@@nishanttyagi3665it has something to do with the way memory works at lower level. If you have to make an array of size SxL make it as array[S][L] instead of array[L][S], where S is the smaller and L is the larger dimension respectively. It is a bit faster.
@@_bittu_ I read this on stackoverflow too. This is correct thank you.
@@_bittu_ Thanks!
Understood
understood