### shubro18's blog

By shubro18, history, 3 weeks ago, I submitted a dp solution to problem 996A of Hit The Lottery. I didnt find any error in my code and logic seems to be fine. Can someone tell me why am I getting this error. I am new to CP and would appreciate if the nuances are clearly highlighted to me.

#include<bits/stdc++.h>
using namespace std;
#define min(a,b) ((a<=b)?a:b)
typedef long long ll;
int main()
{
vector<long long int> v1 = {1, 5, 10, 20, 100};
long long int n;
cin>>n;
vector<long long int> dp(n+1,0);
dp = 1;
long long int min;
for(int i = 1;i<=n;i++)
{
min = dp[i - 1] + 1;
for(auto j:v1)
{
if(j<=i&&(dp[i - j]+dp[j]<min))
{
min = dp[i - j] + dp[j];
}
}
dp[i] = min;
}
cout<<dp[n];
return 0;
}  Comments (13)
 » Auto comment: topic has been updated by shubro18 (previous revision, new revision, compare).
 » Auto comment: topic has been updated by shubro18 (previous revision, new revision, compare).
 » do you really know what for:auto is for?
•  » » Roughly, as far as I know it points to the value inside the vector and automatically detects the data type of the values. I managed to get some test cases right which I entered myself. for 100 I got 1, for 43 I got 5, for 25 I got 2, for 200 I got 2. The error occurred when I ended up putting 1000000 as a test case.
•  » » » for(int j = 0; j < (sizeof(v1)/sizeof(v1); j++) does not equal to for(auto j:v1) man
•  » » » » I know that sir. j is the value inside the vector. I am not using j for the very purpose that you have written. j is the value of the denomination.
•  » » » » » 3 weeks ago, # ^ | ← Rev. 2 →   My mistake, sr my bad In that case, maybe in got exceeded on test n = 10^9 Normally arrays can hold up to 10^7, however there are some exceptions, but maybe not this problem
 » When n = 1e9, you are exceeding the memory limit.
•  » » So any suggestion as to how I can rectify the code coz the logic is correct. And n = 1e9 is one of the test cases
•  » » » DP is an overkill for this particular problem, because the problem can be solved by using a simple greedy algorithm. And it can be easily proven that a greedy algorithm is guaranteed to be optimal in this case.As for the logic being correct. For example, using bubble sort is also a correct solution if you want to sort an array. Except that it's likely to be way too slow for large arrays.But the problem can be generalized to be solvable for any set of arbitrary fancy bills (each of them having nominal value up to but not exceeding 100 dollars) and in this case it would need DP for real. And reducing memory usage becomes necessary. Is this what you are interested in?
•  » » » » Yes I actually ended up considering this problem to be the one that you talked about at the end of your reply. So memory usage optimization is something I am interested in.