hey there. do you want to see the recursive version?? #include
using namespace std; const int bpr = 1e9+7; // Big Prime long long no_of_ways(long long sum, int i, vector &cns, vector &dp){ if(sum == 0) return 1; if(sum < 0 or i < 0) return 0; if(dp[sum][i] != -1) return dp[sum][i]; long long op1 = no_of_ways(sum, i-1, cns, dp); long long op2 = no_of_ways(sum-cns[i], i, cns, dp); dp[sum][i] = (op1%bpr + op2%bpr)%bpr; return dp[sum][i]; } int main(){ long long n, s; cin >> n >> s; vector cns(n); for(int i=0; i> cns[i]; sort(cns.begin(), cns.end(), greater()); vector dp(s+1, vector(cns.size(), -1)); long long ans = no_of_ways(s, cns.size()-1, cns, dp); cout
i was seeing your rating curve and it increased steeply what did you do in that period of time because i am kind of stuck in between specialist and expert on codeforces
I learnt new techniques which earlier I wasn't aware of. I recommend "codechef prepare" advanced section syllabus and Practicing problems from CF/CC which are a little above your current level. I also feel that I gained a lot by explaining the things I have Learnt to my friends and later became a mentor at CB which again helped my understanding of Concepts get better because I feel you only understand something well if you can explain it to a layman. Moreover I really enjoy sharing my knowledge and understanding with others in a crisp and clear manner, apart from CB i wrote some good blogs on CF and now have finally started this YT channel.
Great video. Thank you. I had a query though. Here, to avoid the issue of double counting, we added another variable to the state of dp which tells us which coin we are currently at and we decide whether we take it or not. Reading online I came across a O(n) space solution. It gives the correct answer without any additional state parameter. I do not get why it works though. Can you provide any insights on it? The code is as follows:- // dp[i] is ways to get sum x. for ( int c: coins) { for( int i=1; i= 0) { dp[i] += dp[i-c]; dp[i] %= mod; } } } Thanks again.
Thanks Naveen. Even the solution Discussed in the video can be optimized to O(target) space instead O(n*target) because if you look at the table more clearly, dp[i] depends only upon dp[i-1], so all you need is one past vector state instead of all past vector states. I'll check the code provided by you in a while.
Hello bhaiyah! A big fan of your explaination. I used long long, and it showed RUNTIME on some test case, but when I used int, it showed accepted. How is this possible? Shouldn't it be the other was round?
I have a little doubt, for n = 5 , two possible ways are 2 2 1 and 1 2 2. Why the dp solution consider both of them as a one way & take the count as 1? Meanwhile I implemented this and got AC: int dice(int n) { if(n == 0) return 1; if(n < 0) return 0; if(dp[n]!=-1) return dp[n]; return dp[n] = (dice(n-1)%MOD+dice(n-2)%MOD+dice(n-3)%MOD+dice(n-4)%MOD+dice(n-5)%MOD+dice(n-6)%MOD)%MOD; }
hello bhaiya, nice video! although i really want to clear one thing out. whenever I encounter a DP problem, i try to come up with a recursive solution and also memoize it later on and in most cases i am always succesfull. but i have observed that the above mentioned format of the solution will ALWAYS lead to runtime error due to stackoverflow error (for very large inputs, of course) so is it not advisable to go on with this solution and to just think iteratively? please bhaiya respond. thanks for this amazing content
hey! see the most important thing when solving a DP problem is the recurrence. Once you have the recurrence you can implement it either top-down or bottom-up. usually people find implementing bottom-up a bit harder since there is a topological sort ordering of dp-states that needs to be obeyed. Just make sure you understand the recurrence and then go with any of the implementations.
@@AlgosWithKartik yes I understand that. But it seems to me that recursive solutions are very rarely submitted for these type of questions since they lead to stackoverflow error almost every time (even after memoizing). Is this the case for everyone or am I doing something wrong? Even in question discussed in the video I tried to submit my recursive + memoized solution and it worked for smaller inputs but stackoverflowed for very large inputs
@@haiaus9054 the time and mem limits at cses platform are really tight. On other platforms I would expect a top-down solution to pass easily given that it has the same asymptomatic time and space complexities as the bottom-up counterpart which gets an AC. So yes bottom up codes are more efficient, however top-down should be acceptable at many places if not all.
Hi Soham, this will ensure that the choices are ordered because if in a way you are going to select the ith coin then you will always select the ith coin before selecting a coin with a smaller index/value. So if your coins were 2,5,7 And you want to write X as a sum of these coins, if at all you use the coin with value 7 you will always use coin 7 before using either 2 or 5. So X = 7 + something + something And never will you count the way in which X = 5 + 7 + something. So the idea is use the rightmost coin 1st and if you choose not to use it, you will lose the option of using it again thus ensuring the choices will be ordered: largest coin -> smallest coin. If you still have a doubt let me know.
Getting runtime error in some cases! Please help: Here is my code: #include //#define int long long #define f(i,a,b) for(int i=a;ia[i]; } int dp[n+1][x+1]; for(int i=1;i
As long as I have enough memory to store my array in, It's alright to create even larger sized arrays. 10^8 integers = 4x10^8 bytes = 4x10^5 KB = 4*10^2 MB = 400MB Allowed memory as per the platform is 512MB
I came up with a single dp state recursive memorization solution that works. The approach is different but it works for all tc. Seeing your solution, I doubt if my solution is even dp. Could you take a look and tell me why it works?
Bro can you explain how to know that we use 1D dp or 2D dp and also how to decide which things(number of coins or sum) used for outer loop and other for inner loop??
you can interchange loops. this is code after interchanging the loop. #include using namespace std; const int mod = 1000000007; int dp[1000001][101]; signed main() { ios_base::sync_with_stdio(0); cin.tie(0); int t; t = 1; while (t--){
int n, X; cin>>n >>X;
int arr[n]; for(int i = 0; i < n; i++) cin>>arr[i];
Thank you very much bhai I always used long long instead of int and get stucked in this case and getting Runtime error but can you explain why we are getting Runtime error? is it because of exceeding space complexicty??
@@himanshuyadav1875 Yes, it's probably exceeding the memory limit. The memory limit in the problem is 512 MB which is around 5.4* 10^8 bytes. If we use long long, which takes 8 bytes, we can declare an array of maximum size around 6.7*10^7. And for int we get 1.3* 10^8. In my case, I declared ll dp[110][10^6], so a total of 10^8. I guess that's why I was getting the runtime error.
Please make one video How to print all coins that makes the sum. Like for n=5 a={1, 2, 3} it should print all ways that sum 5 can be made 1 1 1 1 1 1 2 2 1 1 3 and so on
![[CSES][Dynamic Programming] Book Shop](http://i.ytimg.com/vi/MEXBU9SFy7Q/mqdefault.jpg)
Thankyou for the series, please continue adding more content.
This is very helpful!!
Glad you liked it :)
Sure I'll keep adding more, stay tuned.
YOU ARE ONE OF THE BEST PROGRAMMERS OUT THERE!
thankyou so much Namita :)
Hey I have written similar code but it is showing runtime error for larger sum values
Were you able to solve it?
use int only not long long int
I haved solved this question earlier with a different approach. But approach is 🔥🔥
Great great content!!! Please keep them coming
For anyone getting a runtime error on some test cases. Just remove long long and use normal integer..
can you explain to me, why this is showing a runtime error?
your explanation is lit bro..keep it up
Thanks bro!
awesome explanation
Thanks a lot sir....can you please add videos on graph cses problems it will be really helpful
Best explanation
hey there. do you want to see the recursive version??
#include
using namespace std;
const int bpr = 1e9+7; // Big Prime
long long no_of_ways(long long sum, int i, vector &cns, vector &dp){
if(sum == 0)
return 1;
if(sum < 0 or i < 0)
return 0;
if(dp[sum][i] != -1)
return dp[sum][i];
long long op1 = no_of_ways(sum, i-1, cns, dp);
long long op2 = no_of_ways(sum-cns[i], i, cns, dp);
dp[sum][i] = (op1%bpr + op2%bpr)%bpr;
return dp[sum][i];
}
int main(){
long long n, s;
cin >> n >> s;
vector cns(n);
for(int i=0; i> cns[i];
sort(cns.begin(), cns.end(), greater());
vector dp(s+1, vector(cns.size(), -1));
long long ans = no_of_ways(s, cns.size()-1, cns, dp);
cout
it will give tle bro
@@ShubhamKumar-ot4bc yes! But i just posted just to point out the recursive version too. 😊🤝🤝
size of dp array is 100*(10^6) in worst case. Is it valid? or the test cases are weak
same doubt, there is one test case where n=100 and x=1e6, i dont know how it works. Please help if you have an explanation
i was seeing your rating curve and it increased steeply what did you do in that period of time because i am kind of stuck in between specialist and expert on codeforces
I learnt new techniques which earlier I wasn't aware of.
I recommend "codechef prepare" advanced section syllabus and Practicing problems from CF/CC which are a little above your current level.
I also feel that I gained a lot by explaining the things I have Learnt to my friends and later became a mentor at CB which again helped my understanding of Concepts get better because I feel you only understand something well if you can explain it to a layman.
Moreover I really enjoy sharing my knowledge and understanding with others in a crisp and clear manner, apart from CB i wrote some good blogs on CF and now have finally started this YT channel.
Great content...please upload more in dp series....
Definitely!!
Nice explanation bro🔥🔥
Very well explained
Thanks, Kartik, It helped.
Great video. Thank you. I had a query though. Here, to avoid the issue of double counting, we added another variable to the state of dp which tells us which coin we are currently at and we decide whether we take it or not.
Reading online I came across a O(n) space solution. It gives the correct answer without any additional state parameter. I do not get why it works though. Can you provide any insights on it? The code is as follows:-
// dp[i] is ways to get sum x.
for ( int c: coins)
{
for( int i=1; i= 0)
{
dp[i] += dp[i-c];
dp[i] %= mod;
}
}
}
Thanks again.
Thanks Naveen.
Even the solution Discussed in the video can be optimized to O(target) space instead O(n*target) because if you look at the table more clearly, dp[i] depends only upon dp[i-1], so all you need is one past vector state instead of all past vector states.
I'll check the code provided by you in a while.
Hello bhaiyah! A big fan of your explaination. I used long long, and it showed RUNTIME on some test case, but when I used int, it showed accepted. How is this possible? Shouldn't it be the other was round?
our total space if 100*1000000
memory -> 10^8 * 8 = 800MB LL
memory-> 10^8 * 4 = 400 MB Int
memory limit 512 hai
Just wanna say "Op"
i am not getting the "excluding the coin part", op2 = (i==1)?0:dp[i-1[sum]......
I have a little doubt, for n = 5 , two possible ways are 2 2 1 and 1 2 2. Why the dp solution consider both of them as a one way & take the count as 1?
Meanwhile I implemented this and got AC:
int dice(int n)
{
if(n == 0)
return 1;
if(n < 0)
return 0;
if(dp[n]!=-1)
return dp[n];
return dp[n] = (dice(n-1)%MOD+dice(n-2)%MOD+dice(n-3)%MOD+dice(n-4)%MOD+dice(n-5)%MOD+dice(n-6)%MOD)%MOD;
}
thankyou
Great sir. Boon for me.
great video
Brother ..huge thumbs up for your effort . But it's showing so many ads in between videos. Can you please minimize it...Because at times its annoying
BTW statement change hogyaa hai :) uska ans linear dp ya 1D dp se ata hai
Bro I am getting TLE in n*x solution.
sir while doing the recursive +memoisation solution i am getting runtime error in some test cases....
Hi Gunjan, share the code with me and I'll have a look :)
@@AlgosWithKartik #include
using namespace std;
#define iint int
#define f(i,a,b) for(ll i=a;i=b;i--)
#define for1(i,n) for(ll i=1;i>t;while(t--)
#define lol std::ios::sync_with_stdio(false); cin.tie(NULL);
#define endl "
"
#define mp make_pair
#define ss second
#define ff first
#define ll long long
#define int long long
#define pii pair< int,int >
#define pll pair< ll,ll >
#define sz(a) a.size()
#define inf (1000*1000*1000+5)
#define all(a) a.begin(),a.end()
#define arr(a,n) int a[n];f0(i, n) cin >> a[i];
#define ini(a,n) memset(a,n,sizeof(a))
#define rr return 0;
#define vint vector< int >
#define l_b lower_bound
#define u_b upper_bound
#define mod 1000000007
#define pi 3.141592653589793238
#define fmap(m) for(auto it:m)
#define deb(x) cout
Ik i am quite late but I am also facing the same problem . Pls share the code if possible and what was wrong with it?
I have a doubt. How is the space complexity O(NX) here? It should have just been O(N) right? to store the coin values??
hello bhaiya, nice video!
although i really want to clear one thing out.
whenever I encounter a DP problem, i try to come up with a recursive solution and also memoize it later on and in most cases i am always succesfull.
but i have observed that the above mentioned format of the solution will ALWAYS lead to runtime error due to stackoverflow error (for very large inputs, of course)
so is it not advisable to go on with this solution and to just think iteratively?
please bhaiya respond. thanks for this amazing content
hey! see the most important thing when solving a DP problem is the recurrence. Once you have the recurrence you can implement it either top-down or bottom-up. usually people find implementing bottom-up a bit harder since there is a topological sort ordering of dp-states that needs to be obeyed.
Just make sure you understand the recurrence and then go with any of the implementations.
@@AlgosWithKartik yes I understand that. But it seems to me that recursive solutions are very rarely submitted for these type of questions since they lead to stackoverflow error almost every time (even after memoizing). Is this the case for everyone or am I doing something wrong? Even in question discussed in the video I tried to submit my recursive + memoized solution and it worked for smaller inputs but stackoverflowed for very large inputs
@@haiaus9054 the time and mem limits at cses platform are really tight. On other platforms I would expect a top-down solution to pass easily given that it has the same asymptomatic time and space complexities as the bottom-up counterpart which gets an AC.
So yes bottom up codes are more efficient, however top-down should be acceptable at many places if not all.
I also got the same type of Tle i.e. run time error through memoized code in more than 1 ques
Is a recursive solution for this problem not possible because my recursive code works for smaller test cases but not larger ones
yes same problem. My memoization code is also not working
I dont really understand how this ensures that the choices will be ordered :/
Hi Soham, this will ensure that the choices are ordered because if in a way you are going to select the ith coin then you will always select the ith coin before selecting a coin with a smaller index/value.
So if your coins were 2,5,7
And you want to write X as a sum of these coins, if at all you use the coin with value 7 you will always use coin 7 before using either 2 or 5.
So X = 7 + something + something
And never will you count the way in which X = 5 + 7 + something.
So the idea is use the rightmost coin 1st and if you choose not to use it, you will lose the option of using it again thus ensuring the choices will be ordered: largest coin -> smallest coin.
If you still have a doubt let me know.
@@AlgosWithKartik got it! Thanks :)
Getting runtime error in some cases! Please help:
Here is my code:
#include
//#define int long long
#define f(i,a,b) for(int i=a;ia[i];
}
int dp[n+1][x+1];
for(int i=1;i
you are creating a array of size 100 *10^6 , how is it possible
As long as I have enough memory to store my array in, It's alright to create even larger sized arrays.
10^8 integers = 4x10^8 bytes = 4x10^5 KB = 4*10^2 MB = 400MB
Allowed memory as per the platform is 512MB
@@AlgosWithKartik thanks for the explanation.. i was doing this in the coding blocks online IDE. it was not working. Got it now....
Which book/ blog did you used to learn all this?
Is this top down or bottom up approach sir ??
Bottom up
@@jatinaggarwal9965 Thank you bro
@@borrarohit324 any time
Bhaiya why don't you frequently put such problemset now.
I came up with a single dp state recursive memorization solution that works. The approach is different but it works for all tc. Seeing your solution, I doubt if my solution is even dp. Could you take a look and tell me why it works?
#define LL long long
LL n;
LL c[100];
LL dp[1000000];
LL x;
LL solve(LL sum) {
if (sum == x)
return 0;
if (sum > x)
return INT_MAX;
if (dp[sum] != -1)
return dp[sum];
LL ans = INT_MAX;
for (int i = 0; i < n; i++) {
ans = min(ans, solve(sum + c[i]) + 1);
}
return dp[sum] = ans;
}
void MAIN() {
memset(dp, -1, sizeof(dp));
cin >> n >> x;
for (int i = 0; i < n; i++)
cin >> c[i];
LL ans = solve(0);
(ans < INT_MAX) ? cout
yes definitely looks like dp to me.
always try to build a recurrence, that will help you have a better understanding.
I just realized that I was talking about a different question "minimizing coins". My bad
I am confused between coin combinations one and two
Bro can you explain how to know that we use 1D dp or 2D dp and also how to decide which things(number of coins or sum) used for outer loop and other for inner loop??
you can interchange loops. this is code after interchanging the loop.
#include
using namespace std;
const int mod = 1000000007;
int dp[1000001][101];
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int t;
t = 1;
while (t--){
int n, X;
cin>>n >>X;
int arr[n];
for(int i = 0; i < n; i++) cin>>arr[i];
for(int x = 0; x
Hi bro , U can teach in Java right ! Can you do it
Priyansh agarwal from tle eliminators copying your content xd
Anyone getting Runtime error, change long long dp[n+1][x+1] to int dp[n+1][x+1], it will hopefully work.
Thank you very much bhai
I always used long long instead of int and get stucked in this case and getting Runtime error
but can you explain why we are getting Runtime error?
is it because of exceeding space complexicty??
@@himanshuyadav1875 Yes, it's probably exceeding the memory limit.
The memory limit in the problem is 512 MB which is around 5.4* 10^8 bytes. If we use long long, which takes 8 bytes, we can declare an array of maximum size around 6.7*10^7. And for int we get 1.3* 10^8.
In my case, I declared ll dp[110][10^6], so a total of 10^8. I guess that's why I was getting the runtime error.
Please make one video
How to print all coins that makes the sum. Like for n=5 a={1, 2, 3} it should print all ways that sum 5 can be made
1 1 1 1 1
1 2 2
1 1 3 and so on