### 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[0] = 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;
}


• 0

 » 3 weeks ago, # |   0 Auto comment: topic has been updated by shubro18 (previous revision, new revision, compare).
 » 3 weeks ago, # |   0 Auto comment: topic has been updated by shubro18 (previous revision, new revision, compare).
 » 3 weeks ago, # |   0 do you really know what for:auto is for?
•  » » 3 weeks ago, # ^ |   0 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.
•  » » » 3 weeks ago, # ^ |   0 for(int j = 0; j < (sizeof(v1)/sizeof(v1[0]); j++) does not equal to for(auto j:v1) man
•  » » » » 3 weeks ago, # ^ |   +1 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 →   0 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
 » 3 weeks ago, # |   0 When n = 1e9, you are exceeding the memory limit.
•  » » 3 weeks ago, # ^ |   0 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
•  » » » 3 weeks ago, # ^ |   +5 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?
•  » » » » 3 weeks ago, # ^ |   0 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.