SPOJ COINS

From Algorithmist

[edit] 346 - Bytelandian gold coins

• http://spoj.sphere.pl/problems/COINS

[edit] Summary

The main question in this problem is how to get optimal exchange value of coins. If you have coin with value n, you could exchange directly to get value n, or choose to exchange it first into 3 other coin values i.e n/2, n/3 and n/4.

[edit] Explanation

One of the simplest way to solve this problem is using memoization. Sub problem relations clear from the summary is that for each value n you have to choose maximum between n and its exchange values i.e :

[edit] Implementation

Just implement the recurrence described above using memoization. Although the constraint seems high : 0 <= n <= 1000 000 000, it shows that for 1000000000 with memoization, this recurrence is only evaluated 754 times.

To get an approximate count on the recurrence, realize that at any state corresponds to some division of n by 2s and 3s. Any division by 4 is just a repeated division by 2. How many ways can we divide 1000 000 000 by 2? Approximately log₂(1000000000). And how many times can we divide 1000 000 000 by 3? Approximately log₃(1000000000). Since the division operations are independent, have have log₂(1000000000) * log₃(1000000000) = 552.

We will be well within time limits.

Use the class map of the STL in C++. See.

//C++ code
 
#include<map>
 
using namespace std;
 
map <int , long long> h;
 
long long f(int n) //precondition -> h.clear() 
{
  if (n == 0) return 0; //base
 
  long long r = h[n];
 
  if (r == 0) 
  {
    r = MAX( n , f(n/2)+f(n/3)+f(n/4) );
    h[n] = r;
  }
 
  return r;
}

[edit] Input

12
1000000000

[edit] Output

13
4243218150