@@JIGARSINGTHAKOR-yy6qp bro yt is automatically deleting the comment containing link so here is the code -> #include using namespace std; #ifndef ONLINE_JUDGE #include "debug.h" #else #define dbg(...) ; #define debug(...) ; #define crndl ; #endif mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count()); using vi = vector; using pi = pair; #define endl " " #define pb push_back #define all(x) begin(x), end(x) #define sz(x) (int) (x).size() #define f first #define s second #define mp make_pair #define int long long const int mod=1e9+7; const long long INF=LLONG_MAX >> 1; int n,k; int c[1000009]; int dp[1000009]; int solver(int sum){ if(sum n >> k; for(int i=0;i> c[i]; memset(dp,-1,sizeof(dp)); int yohooo=solver(k); cout > t; for(int _=1;_
Really interesting way of solving DP question... I always wondered how top coders directly solve via top down approach. Probably this is how they do it .
Here is the recursive code if we consider same meaning of your state and transition int count(int target, vector &values, vector &dp) { if(target == 0) return 0; if(dp[target] != -1) return dp[target]; int coins = 1e9; for(int j = 0; j < values.size(); j++) if(target >= values[j]) coins = min(coins, count(target - values[j], values, dp) + 1); return dp[target] = coins; }
not my code #include using namespace std; const int MOD = 1000000007; // Function to calculate the number of ways to return to vertex D in n steps long long func(int n) { // dp[i][j] represents the number of ways to be at vertex j after i steps vector dp(n+1, vector(4, 0)); // Base case: at step 0, the ant is at vertex D dp[0][3] = 1; // D is indexed as 3 // Transition for (int i = 1; i > n; cout
Day03 with Tle Eliminators Priyansh Bro You Missed With Link it is jump to dice Combination Instead of Minimizing Coins problem please fix it and Can you provide some Addtional TestCase for Dry Run for better Understanding Thank You 😊😊 Give me One tese Case if available
Thanks for reporting. Updated the link. As for a test case you can consider this example: n = 3, x = 10 coins = {4, 2, 6} Try dry running the code on this on your own. In case you face any issues, feel free to ask here.
sir i want ur sugeestion now i am in third year i am not feeling well in second year i solved leetcode and striversheets and all not improved problem solving in dev part i am not getting much interest and in 5 sem passedbecause of depression i stayed alone in my college may this backfired me so can u suggest now how to continue my journey
Firstly, don't worry about the past, what's done is done. Focus on what's coming ahead. Now, if you're going to sit for placements in the upcoming 2-3 months just focus on DSA. If not, you can work on building your problem solving skills. Attempt a lot of CF and Leetcode contests. Don't worry if you're not able to solve them, just try to upsolve 1-2 problems after every contest. The whole idea is that if you have very less time remaining, focus on just DSA otherwise you can do CP and work on DSA in the last 3 months, by then your problem solving skills be so good that DSA would be a cakewalk.
@@TLE_Eliminators And for development what should I do sir any suggestion I know basics of html ,css,js and little bit reactjs with the little knowledge knowledge on webdev I am not able to implement creative ideas on my own and college pressure i am not able to manage all these and cs fundamentals DBMS and OS literally our teaching is very bad so even I am not getting interest in studying and sleeping whole day and getting anxiety not feeling well can u tell me to get out of this what should I do sir
What is the meaning of your state? What do your transitions mean? What is the time complexity of this code? Can you answer the above questions so that I can help you better?
@@PriyanshAgarwal dp[i][j] here means the minimum no. of coins possible when the sum of coins is j and only first i type of coins to be used. T.C here is n*x
Also the transition here means that if the (i-1)th denomination is less than or equal to sum j (remaining sum of money) then we can either choose that coin( 1+dp[i][j-a[i-1]]) or reject( dp[i-1][j] ) it but if it is greater than the sum j then we must reject it.(dp[i-1][j])
Bhaiya I tried to implement it recursively by Memorization, but it's giving me TLE... The time it will take will also be O(n*x), then why I get TLE? Here is my code -- #include using namespace std; #define endl ' ' const long long MOD = 1e9 + 7; const long long INF = LLONG_MAX >> 1; int fun(vector &arr,int n, vector &dp, int X){ if(X < 0) return 1e9; if(X == 0) return 0; if(dp[X] != 1e9) return dp[X]; for(int i=0;i= 0){ int res = fun(arr,n,dp,X - arr[i]) + 1; dp[X] = min(dp[X] , res); } } return dp[X]; } int main(){ ios::sync_with_stdio(false); cin.tie(NULL); // Your code here int n,x; cin >> n >> x; vector arr(n); for(int i=0;i> arr[i]; vector dp(x + 1, 1e9); // dp[i] -> minimum coins to generate a sum of i int ans = fun(arr,n, dp, x); cout
CSES has a strict time limit which only allows for iterative solutions to pass in a lot of DP problems. Please try to code it iteratively as explained by Priyansh in the video.
Using your method i am able to code both recursive and iterative
That is exactly what was intended. Hopefully you will be able to do the same for harder problems.
Can you please share your recursive code i got tle in 2 test cases
@@JIGARSINGTHAKOR-yy6qp bro yt is automatically deleting the comment containing link
so here is the code ->
#include
using namespace std;
#ifndef ONLINE_JUDGE
#include "debug.h"
#else
#define dbg(...) ;
#define debug(...) ;
#define crndl ;
#endif
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
using vi = vector;
using pi = pair;
#define endl "
"
#define pb push_back
#define all(x) begin(x), end(x)
#define sz(x) (int) (x).size()
#define f first
#define s second
#define mp make_pair
#define int long long
const int mod=1e9+7;
const long long INF=LLONG_MAX >> 1;
int n,k;
int c[1000009];
int dp[1000009];
int solver(int sum){
if(sum n >> k;
for(int i=0;i> c[i];
memset(dp,-1,sizeof(dp));
int yohooo=solver(k);
cout > t;
for(int _=1;_
Really interesting way of solving DP question... I always wondered how top coders directly solve via top down approach. Probably this is how they do it .
Thanks, we believe you meant bottom up (and not top down xD)
@@TLE_Eliminators 🤣
understood :) best channel so far , TLE will be big in future!
Quality content,Please tell your other instructors to use board like this and a clear mic,their content quality is below average
Loved ur way of teaching
very easy to understand , thanks
Here is the recursive code if we consider same meaning of your state and transition
int count(int target, vector &values, vector &dp)
{
if(target == 0)
return 0;
if(dp[target] != -1)
return dp[target];
int coins = 1e9;
for(int j = 0; j < values.size(); j++)
if(target >= values[j])
coins = min(coins, count(target - values[j], values, dp) + 1);
return dp[target] = coins;
}
bro why it is not working provide output 0
understood!!
Thanks :)
Amazing Bhaiya... Nice explanation
I got solution to this problem recursively but can't think of dp implementation code...will see solution after trying for 1 hr bhaiya
Fantastic ... Your are joss vai
Great explanation
The most optimal solutions are causing TLE in Python . the same goes with this also.
Are you coding this iteratively or recursively?
Try using cpp.
Same happened with me with java.
@@TLE_Eliminators iteratively only
In cses problem set time limit is very tight and test case also so you have to use cpp
Don't worry if your solution has desired complexity , it will get pass , you can try submitting multiple times.
UNDERSTOOD
Hiey Priyansh can you provide solution for the 2nd problem which tetrahedron i can't recognize the answer after reading the editorial also Thank you
not my code
#include
using namespace std;
const int MOD = 1000000007;
// Function to calculate the number of ways to return to vertex D in n steps
long long func(int n) {
// dp[i][j] represents the number of ways to be at vertex j after i steps
vector dp(n+1, vector(4, 0));
// Base case: at step 0, the ant is at vertex D
dp[0][3] = 1; // D is indexed as 3
// Transition
for (int i = 1; i > n;
cout
Understood..❤
Coool
Done!
# UNDERSTOOD
amazing sir
Understood..!!
Thank you!
Understood!!
Understood
understood
i defined my state as dp(i,sum) - from ith index min no of coins required to form sum but this is giving run time error why is this so ?
check my comment
Day03 with Tle Eliminators Priyansh Bro You Missed With Link it is jump to dice Combination Instead of Minimizing Coins problem please fix it and Can you provide some Addtional TestCase for Dry Run for better Understanding Thank You 😊😊 Give me One tese Case if available
Thanks for reporting. Updated the link.
As for a test case you can consider this example:
n = 3, x = 10
coins = {4, 2, 6}
Try dry running the code on this on your own. In case you face any issues, feel free to ask here.
@@TLE_Eliminators Sure Sir and Thank You so Much 😊😊
understood ^.^
❤
bhaiya can also tell the recursive method
Try coding the problem on your own.
sir i want ur sugeestion now i am in third year i am not feeling well in second year i solved leetcode and striversheets and all not improved problem solving in dev part i am not getting much interest and in 5 sem passedbecause of depression i stayed alone in my college may this backfired me so can u suggest now how to continue my journey
Firstly, don't worry about the past, what's done is done. Focus on what's coming ahead.
Now, if you're going to sit for placements in the upcoming 2-3 months just focus on DSA. If not, you can work on building your problem solving skills. Attempt a lot of CF and Leetcode contests. Don't worry if you're not able to solve them, just try to upsolve 1-2 problems after every contest.
The whole idea is that if you have very less time remaining, focus on just DSA otherwise you can do CP and work on DSA in the last 3 months, by then your problem solving skills be so good that DSA would be a cakewalk.
@@TLE_Eliminators And for development what should I do sir any suggestion I know basics of html ,css,js and little bit reactjs with the little knowledge knowledge on webdev I am not able to implement creative ideas on my own and college pressure i am not able to manage all these and cs fundamentals DBMS and OS literally our teaching is very bad so even I am not getting interest in studying and sleeping whole day and getting anxiety not feeling well can u tell me to get out of this what should I do sir
@@abc-ym4zs you okay brother?
min(dp[i], dp[i-v[j]] +1 ); this thing "dp[i-a[j]]" is not coming in my brain on my own. Rest understoop the solution
a[j] is the value of the jth coin that you're using here
so now instead of constructing i, you will consider i - a[j]
can someone pls tell why am I getting runtime error in some test cases : #include
#define endl "
"
#define Y cout
What is the meaning of your state? What do your transitions mean?
What is the time complexity of this code?
Can you answer the above questions so that I can help you better?
Is it because the array size gets exceeded the limit of continuous memory allocation?
@@PriyanshAgarwal dp[i][j] here means the minimum no. of coins possible when the sum of coins is j and only first i type of coins to be used.
T.C here is n*x
Also the transition here means that if the (i-1)th denomination is less than or equal to sum j (remaining sum of money) then we can either choose that coin( 1+dp[i][j-a[i-1]]) or reject( dp[i-1][j] ) it but if it is greater than the sum j then we must reject it.(dp[i-1][j])
#day3
idk why but this looks like greedy lol "Understood"
Bhaiya I tried to implement it recursively by Memorization, but it's giving me TLE... The time it will take will also be O(n*x), then why I get TLE?
Here is my code --
#include
using namespace std;
#define endl '
'
const long long MOD = 1e9 + 7;
const long long INF = LLONG_MAX >> 1;
int fun(vector &arr,int n, vector &dp, int X){
if(X < 0) return 1e9;
if(X == 0) return 0;
if(dp[X] != 1e9) return dp[X];
for(int i=0;i= 0){
int res = fun(arr,n,dp,X - arr[i]) + 1;
dp[X] = min(dp[X] , res);
}
}
return dp[X];
}
int main(){
ios::sync_with_stdio(false); cin.tie(NULL);
// Your code here
int n,x;
cin >> n >> x;
vector arr(n);
for(int i=0;i> arr[i];
vector dp(x + 1, 1e9);
// dp[i] -> minimum coins to generate a sum of i
int ans = fun(arr,n, dp, x);
cout
CSES has a strict time limit which only allows for iterative solutions to pass in a lot of DP problems. Please try to code it iteratively as explained by Priyansh in the video.
awesome explanation
Understood
Understood