Coin change (coin values are powers of m)

Question

Below problem was in a contest (it's over now) contest link.

Its seems variant of classic coin denomination problem - Given an array(k elements) having coin values and a number n. We need to answer the number of ways we can make the denomination of n. we can solve it by DP which will take O(n*k) time. Now in contest problem instead of giving coin value array, there is a value m, and coin values are all possible powers of m ex. n= 200, m=3. so we have coin values with [3^0, 3^1, 3^2, 3^3, 3^4], higher powers are not useful for the example].

I used DP approach here but its giving TLE. By seeing the time limit testcases<=10000, n<=10000, m<=10000, I assume we have to solve it for given n,m in O(n) time[may need to optimize this one also. Please help me to solve this problem. My solution using DP.

#include <bits/stdc++.h>
#include <stdio.h>

using namespace std;

int solve(vector<int>&vec, int n){
    cout<<"n= "<<n<<": m= "<<vec.size()<<endl;
    int r=n+1, c=vec.size()+1;
    vector<int>row(c,0);
    vector<vector<int> >dp(r, row);
    for(int i=0;i<c;i++)
        dp[0][i]=1;
    for(int i=1;i<r;i++){
        for(int j=1;j<c;j++){
            int a=0;
            if(i-vec[j-1]>=0)
                a=dp[i-vec[j-1]][j];
            dp[i][j]=a+dp[i][j-1];
        }
    }
    return dp[n][c-1];
}

int main()
{
    ios::sync_with_stdio(false);
    int tc,n,m;
    cin>>tc;
    while(tc--){
        cin>>n>>m;
        vector<int>temp;
        int index=0;
        temp.push_back(1);
        while(temp[index]*m<=n){
            temp.push_back(temp[index]*m);
            index++;
        }
        int result=solve(temp,n);
        cout<<result<<endl;
    }
    return 0;
}

Unrelated to the problem, but if you are including anything from `bits` you are doing something wrong - `bits` contains implementation-detail stuff of libstdc++ that is not meant to be included directly. — Matteo Italia, Oct 27 '15 at 22:12
You probably should use the fact that the number of ways to give a sum of n with coins m^0,m^1,m^2... is the same as the number of ways to give m*n with coins m^1,m^2,... — n. m. could be an AI, Oct 29 '15 at 06:36

score 0 · Answer 1 · edited May 23 '17 at 11:46

The "coin change" and similar partitioning problems usually benefit hugely from memoization. I found no clever math trick based on the powers-of-m coin values that could beat a straightforward recursive algorithm with memoization.
(In this answer to a related question I illustrated the impact of memoization on a partitioning algorithm in more detail)

The code example in Javascript below solves the example where n,m = 200,3 in 0.026ms, and the worst case scenario where n,m = 10000,2 in 2.8ms on my i5 desktop; I don't know what the time limit of the competition was, but 10000 random cases take around 3 seconds. And a C++ implementation would of course be much faster.

function coinPowers(n, m) {
    if (n < 1 || m < 1) return 0;
    if (n < m || m == 1) return 1;
    var power = Math.floor(Math.log(n) / Math.log(m));
    var memo = [];
    for (var i = 0; i < n; i++) memo[i] = [];
    return partition(n, m, power);

    function partition(n, m, power) {
        var count = memo[n - 1][power];
        if (count) return count;
        var coin = Math.pow(m, power), count = 1;
        for (var p = power; p > 0; coin /= m, p--) {
            if (coin < n) count += partition(n - coin, m, p)
            else if (coin == n) ++count;
        }
        return (memo[n - 1][power] = count);
    }
}

document.write(coinPowers(200, 3) + "<BR>");
document.write(coinPowers(200, 2) + "<BR>");
document.write(coinPowers(10000, 2) + "<BR>");

Coin change (coin values are powers of m)

1 Answers1