Bytelandian Gold Coin , Dynamic programming , explanation?

Question

It's a bit immature, but I have to ask,

The Bytelandian Gold coin problem mentioned here - http://www.codechef.com/problems/COINS/ , is said to be typical DP problem,even though I have read basics of DP & recursion, but I am finding hard to understand its solution,

 # include <stdio.h>
 # include <stdlib.h>

long unsigned int costArray[30][19];
unsigned int amount;

unsigned int currentValue(short int factor2,short int factor3)
{ 
    int j;
    unsigned int current = amount >> factor2;
    for(j=0;j<factor3;j++)
    current /= 3;
    return current;
}

long unsigned int findOptimalAmount(short int factor2,short int factor3)
{
     unsigned int n = currentValue(factor2,factor3);
    if(n < 12)
    { 
        costArray[factor2][factor3] = n;
        return (long unsigned int)n;
    }
    else
    { 
        if(costArray[factor2][factor3] == 0)
        costArray[factor2][factor3] = (findOptimalAmount(factor2+1,factor3) + findOptimalAmount(factor2,factor3+1) + findOptimalAmount(factor2+2,factor3));
        return costArray[factor2][factor3];
    }
}

int main()
{ 
    int i,j;
    while(scanf("%d",&amount) != EOF)
    { 
        for(i=0;i<30;i++)
        for(j=0;j<19;j++)
            costArray[i][j] = 0;
        printf("%lu\n",findOptimalAmount(0,0));
    }
    return 0;
} 

Like how does its recursion works? How is costArray size is decided to be 30x19?

Also how can I improve my thinking for such problems solving?

Thanks!

Answer 1

your explanation is correct. But the important point here is still unexplained. Here is what f(n) is defined to be

max{ f(n) , f(n/2) + f(n/3) + f(n/4) }

whichever is maximum is the solution for f(n). Digging little further, for all n < 12 f(n) is greater than f(n/2) + f(n/3) + f(n/4). This will become the stopping condition for the recursion. Though at first the above expression may seem a trivial recursion, Its implementation would lead to very inefficient algorithm(reason for not getting accepted on spoj).

We have to some how store the intermediate values of function f such a way that part of the recursive implementation would become lookup of the stored values.

Unfortunately straight storage of the values like memoziation of fibbonaci series would not work for this example. Because in the given program n can reach 1000000000 and we can not create an array of size 1000000000. So here is the clever trick, instead of storing the value of the subproblem directly for every n. We know that n is subdivided by 2(max 30 times) and 3(max 20 times) at every stage(division by 4 is just division by 2 twice), So we will consider a matrix of size 30x20 where an element at index i,j denote the value of n when divided with i times by 2 and j times by 3. This way the given problem f(n) transforms to F(0,0). Now we apply recursion on F and use memoization of the value of n at every stage.

#include<stdio.h>
#define max2(a, b) ((a) > (b) ? (a) : (b))
unsigned long long ff[30][20] = {0};
unsigned long long n = 0;

/* returns value of n when divided by nthDiv2 and nthDiv3 */
unsigned long long current(int nthDiv2, int nthDiv3)
{
    int i = 0;
    unsigned long long nAfterDiv2 = n >> nthDiv2;
    unsigned long long nAfterDiv2Div3 = nAfterDiv2;
    for (i = 0; i < nthDiv3; i++)
        nAfterDiv2Div3 /= 3;
    return nAfterDiv2Div3;
}

unsigned long long F(int nthDiv2, int nthDiv3)
{
    /* if the value of n when divided by nthDiv2 and nthDiv3 is already calculated just return it from table */
    if (ff[nthDiv2][nthDiv3] != 0) 
        return ff[nthDiv2][nthDiv3];
    else {
        //calculate the current value of n when divided by nthDiv2 and nthDiv3 => F(nthDiv2, nthDiv3)
        unsigned long long k1 = current(nthDiv2, nthDiv3);
        if (k1 < 12) /* terminating condition */
            return k1;
        unsigned long long t = F(nthDiv2 + 1, nthDiv3) + F(nthDiv2, nthDiv3 + 1) + F(nthDiv2 + 2, nthDiv3); 
        /* Maximum of F(nthDiv2, nthDiv3) and F(nthDiv2 + 1, nthDiv3) + F(nthDiv2, nthDiv3 + 1) + F(nthDiv2 + 2, nthDiv3) */
        return ff[nthDiv2][nthDiv3] = max2(k1 , t); 
    }
}

int main()
{
    int i, j;
    while (scanf("%llu", &n) != EOF) {
        /* Every testcase need new Memoization table */
        for (i = 0; i < 30; i++)
            for (j = 0; j < 20; j++)
                ff[i][j] = 0;
        printf("%llu\n", F(0, 0));
    }
    return 0;
}