shubro18's blog

By shubro18, history, 3 weeks ago, In English

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;
}
 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by shubro18 (previous revision, new revision, compare).

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by shubro18 (previous revision, new revision, compare).

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

do you really know what for:auto is for?

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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, # ^ |
        Vote: I like it 0 Vote: I do not like it

      for(int j = 0; j < (sizeof(v1)/sizeof(v1[0]); j++) does not equal to for(auto j:v1) man

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        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   Vote: I like it 0 Vote: I do not like it

          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, # |
  Vote: I like it 0 Vote: I do not like it

When n = 1e9, you are exceeding the memory limit.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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, # ^ |
        Vote: I like it +5 Vote: I do not like it

      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, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        • »
          »
          »
          »
          »
          3 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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).

          • »
            »
            »
            »
            »
            »
            3 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Thank you very much for the tips. Just did the greedy solution(a one liner actually).