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;
}
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[0]); 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.
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.
If you look at the 'dp' array usage in your code, then it's possible to notice that only a small rightmost part of it is ever accessed (reading 'dp[j]' values is actually not necessary because each of them is equal to 1). And discarding the ancient history can save a lot of memory. Can you do this?
BTW, if you manage to successfully optimize memory usage, please don't be discouraged by a possible TLE verdict. Running 1000000000 loop iterations is slow. Fixing performance would be the next challenge.
I suggest you to start with implementing a simple greedy solution for the problem 996A. Then verify that your solution is accepted by the system. Then use it to create your own testcases (a bunch of random large N values and the expected correct results for each of them). Then use these testcases to verify correctness of your DP solution on your computer.
Spoiler alert: these are my memory usage and performance adjustments for your DP code: https://codeforces.com/contest/996/submission/113804024 (try not to open this link too early).