Hackerrank DP problem

help
1

I’m solving this Coin Change problem on Hackerrank. I recently started doing DP but stuck on this question.
This is my code:

#include<iostream>
using namespace std;
int main()
{
    int total, n;
    cin>>total>>n;
    int coins[n];
    for(int i=0; i<n; i++) cin>>coins[i];

    int ways[n][total+1] = {0};
    ways[0][0]=1;
    for(int i=1; i<=total; i++)
        if (i % coins[0] == 0)
            ways[0][i]=1;

    for(int i=1; i<n; i++)
    {
        for(int j=0; j<=total; j++)
        {
            if(coins[i]>j)
                ways[i][j] = ways[i-1][j];
            else
                ways[i][j] = ways[i-1][j] + ways[i][j-coins[i]];
        }
    }

    cout<<ways[n-1][total];

    return 0;
}

It gets accepted for most of the test cases but gives weird output on

15 24
49 22 45 6 11 20 30 10 46 8 32 48 2 41 43 5 39 16 28 44 14 4 27 36

this one. And I can’t understand why. Please help.

2

Overflow - try changing the type of ways to long long int.

Edit:

Hmmm … maybe that’s not sufficient - getting weird (but at least not negative!) numbers with this.

1 Like
3

It still produces garbage values…

4

Changing it to use a vector seems to be work: presumably a problem with the two-dimensional array not being zero’d initially correctly:

    vector<vector<long long int>> ways(n, vector<long long int>(total+1));

Edit:

Or alternatively:

    long long int ways[n][total+1] = {};

I’m a bit confused as to why the original was not working - according to this, it seems like maybe it should. Although perhaps it’s because dynamic arrays are non-standard. Dunno :slight_smile:

3 Likes
5

yes, it works. Thanks.

1 Like
6

I wrote a very simple program to demonstrate what goes wrong in your program.

Code 1 
	#include <iostream>

	int main (void) {
		int m, n;
		std::cin >> m >> n;
		int A[m][n] = {0};
		for (int i = 0; i < m; ++i) {
			for (int j = 0; j < n; ++j) {
				if (A[i][j] != 0) {
					std::cout << i << " " << j << std::endl;
				}
			}
		}
		return 0;
	}

I assumed that line 6 creates a ‘variable length array’, which is valid in C, but not valid in C++ and assigns value 0 to all its elements, which straight off causes a compilation error in C:

Code 2 
	#include <stdio.h>

	int main (void) {
		int m, n;
		scanf("%d %d", &m, &n);
		int A[m][n] = {0};
		
		return 0;
	}
Errors and warnings 
progc.c: In function 'main':
progc.c:6:2: error: variable-sized object may not be initialized
  int A[m][n] = {0};
  ^
progc.c:6:17: warning: excess elements in array initializer
  int A[m][n] = {0};
                 ^
progc.c:6:17: note: (near initialization for 'A[0]')
progc.c:6:2: warning: excess elements in array initializer
  int A[m][n] = {0};
  ^
progc.c:6:2: note: (near initialization for 'A')

but somehow doesn’t cause any compilation error in C++.

However, it does cause a run time error. I tested Code 1 with:

Input 
1
500000

Guess what?

Output 
0 498295
0 498296
0 498297
.
.
.

Clearly, it doesn’t assign 0 to all the elements of the array in all cases!

Your task (using Code 1) : Try to figure out the upper-bound of the dimensions so that the program successfully assigns 0 to all the elements. You may try out the fun way by trying out a binary search on the required dimensions or the foolproof way, by going through the assembly (it’s painful but highly rewarding).

[ Warning: The program crashes when you exceed the stack size. ]

Hope this helps. :slightly_smiling_face:

2 Likes