SPOJ COINS

From Algorithmist
Jump to navigation Jump to search

346 - Bytelandian gold coins[edit]

Summary[edit]

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.

Explanation[edit]

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 :

Implementation[edit]

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 . And how many times can we divide 1000 000 000 by 3? Approximately . Since the division operations are independent, have have .

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;
}

Input[edit]

12
1000000000

Output[edit]

13
4243218150

Solutions[edit]

F#: http://adilakhter.wordpress.com/2013/02/26/spoj-346-bytelandian-gold-coins-coins/