Bytelandian Gold Coins (Showing time limit violation)

def max(a,b):
        if a > b :
            return a
        else:
            return b
         
def maximumValue(coinNumber):
        if (coinNumber <= 4 and coinNumber >= 0):
            return coinNumber
        else:
            return max(coinNumber, maximumValue(coinNumber//2) + maximumValue(coinNumber//3) + maximumValue(coinNumber//4))

    while True:
        try:
            coinNumber = int(input())
            print(maximumValue(coinNumber))
        except:
            break

I guess some part of your code is missing. What you wrote is a brute-force solution, whose time-complexity is Exponential.
The Problem can be easily solved using Dynamic Programming. I am not gonna give hint, just try it yourself. :grinning:

1 Like

Please elaborate the concept you used.

Okay, let’s say you have this test case

N = 144

Then, your code runs in this fashion, probably.

                            144 (max(144, 72 + 48 + 36)
                         /   |   \
                      /      |     \
                    /        |       \
max(72, 36+24+18) 72         48        36 max(36, 18+12+9)
             /  |  \       / | \     /  |  \
           36  24  18    24  16 12  18 12  9
            ................................

and it goes on

As you can observe, in the process of calculating Maximum Value for 144, you calculated the same for 72, 48 and 36,…, to calculate same for 72, you calculate same for 36, 24, 18,…, to calculate same for 48, you calculate same for 24, 16, 12, to calculate same for 36, you calculate same for 18, 12, 9 and … :rofl:
YOU ARE REPEATING YOUR SELF
To avoid repeating, you’ll store the values calculated so far somewhere ( may be an array, or hash set, or a dictionary).
Now, this is called Dynamic Programming.
This is a Programming Paradigm used to reduce the time complexity of most of the problems, whose time complexity is exponential (c^n) when solved using brute-force, and involve repeated calculations like the above problem.

Here’s what a typical Python Solution looks like:

dp = dict()
def solve(n):
    if n == 0:
        return 0
    try:
        r = dp[n]
    except:
        c = max(n, solve(n//2) + solve(n//3) + solve(n//4))
        dp[n] = c
        r = c
    return r

def main():
    while True:
        try:
            n = int(input())
            print(solve(n))
        except:
            break

main()

Explanation:

  • First, we initialise a dictionary, which stores key-value pair
  • In this case, key is N and value is the solution for N
  • Initially, this dictionary has nothing
  • But, we dynamically calculate the solution for N’s as we progress
  • For each test case, we do the following:
  1. Read N
  2. Check if we have calculated the solution for this N (using “try-catch” or “in” in Python).
  3. If we have calculated, simply return the solution
  4. Else, solution for this N will be max(N, N/2 + N/3 + N/4). So, we will recursively calculate the solutions for N/2, N/3 and N/4 by repeating the steps 2,3 in similar fashion.
  5. Now, after you calculate the solution for N, don’t forget to store it in the dicionary.

Note that the maximum recursion depth will be log_2 (N), since the smallest number dividing the N is 2.

Hope this is clear, and this is the best way I can explain.
Cheers :grinning:

2 Likes

I didn’t thought that somebody can explain DP such easily. I learnt the concept. Thanks…

1 Like