Recent CP News

# Bytelandian Gold Coins || Hard Problem

## Let’s get some Bytelandian Gold Coins (;

In Byteland they have a very strange monetary system. Each Bytelandian Gold Coins have an integer number written on it. A coin n can be exchanged in a bank into three coins: n/2, n/3 and n/4. But these numbers are all rounded down (the banks have to make a profit).

You can also sell Bytelandian coins for American dollars. The exchange rate is 1:1. But you can not buy Bytelandian coins. You have one gold coin. What is the maximum amount of American dollars you can get for it?

## Input

The input will contain several test cases (not more than 10). Each test case is a single line with a number n, 0 <= n <= 1 000 000 000. It is the number written on your Byteland Gold coin.

## Output

For each test case output a single line, containing the maximum amount of American dollars you can make.

## Explanation

You can change 12 into 6, 4 and 3, and then change these into $6+$4+$3 =$13. If you try changing the coin 2 into 3 smaller coins, you will get 1, 0 and 0, and later you can get no more than $1 out of them. It is better just to change the 2 coin directly into$2.

12
2

13
2

## Solution With Explanation

From the problem definition, say f (n) = ways to compute the change.

f (n) = max (n, f (n / 2) + f (n / 3) + f (n / 4))  (by definition).
f (0) = 0   (Base case).

Problem 1: Writing a simple recursive solution will time out due to exponential complexity i.e. O (3 ).
Problem 2: Writing a linear dynamic programming solution using arrays will exceed memory limit since N can be 10 in the worst case.

To circumvent both of the aforementioned problems, we can use maps and memorization.

Note: This is one of those problems where state space is extra large and memoization only explores space what is needed unlike bottom-up dynamic programming which needs one to visit all the state space, memoization is the preferred solution in this case.

Time Complexity: O (N)
Space Complexity: O (log N)

### Code in C++

// vim:filetype=cpp:foldmethod=marker:foldmarker={{{,}}}

#include <cassert>
#include <cctype>
#include <cmath>
#include <climits>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>

#include <algorithm>
#include <deque>
#include <functional>
#include <iterator>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>

#include <fstream>
#include <iostream>
#include <sstream>

#include <ext/numeric>

using namespace std;
using namespace __gnu_cxx;
// }}}

typedef long long int64;
const int INF = 0x3f3f3f3f;
template <class T> inline int len (const T &a) { return a.size (); }

#define MAXN 50
char line [MAXN];
map <int, int64> memo;

int64
solve (int n) {
if (n == 0 || n == 1) return n;
if (memo.count (n)) return memo [n];
int64 ret = n;
ret = max (ret, solve (n / 2) + solve (n / 3) + solve (n / 4));
return memo [n] = ret;
}

int
main () {
#ifdef LOCALHOST
freopen ("test.in", "r", stdin);
// freopen ("test.out", "w", stdout);
#endif

int N;
while (fgets (line, MAXN, stdin)) {
sscanf (line, "%d", &N);
int64 ret = solve (N);
printf ("%lld\n", ret);
}

return 0;
}

{Code with Code@ter}