CODEWITHSUNDEEP
algorithmmathoptimizationdata-structures
Chad Yu
Chad Yu

Reputation: 21

Find optimal algorithm to reach specific amount of coins in shortest time with cost of upgrading

    I think I met more likely a mathematical problem rather than a algorithm problem. The question description is as follow,

    In a game there's a box that produces 2 coins per second. The goal is to reach A number of coins. It cost B number of coins to upgrade, after which the number of coins produced per second is increased by C, and player can upgrade unlimited number of times by paying B coins. Write code to give optimal upgrades and find shortest runtime for the solution in terms of A, B and C.

    For example, it costs 6 coins to let the box produce 2 more coins per second, and the target is to reach 50 coins. How to determine the best upgrading timing? Appreciate it.

Upvotes: 2

Views: 93

Answers (1)

David Eisenstat
David Eisenstat

Reputation: 65498

If we're going to pay for an upgrade, then we should do it as soon as possible. The kth upgrade thus takes B/(2 + (k-1)*C) seconds, making the pay rate 2 + k*C coins per second. After we're done upgrading, we have to accumulate A coins with our top-of-the-line box. This takes A/(2 + k*C) seconds for a machine that has been upgraded k times.

The savings in completion times in going from k-1 upgrades to k is thus

A/(2 + (k-1)*C) - A/(2 + k*C) - B/(2 + (k-1)*C) =
A*C/((2 + (k-1)*C) * (2 + k*C)) - B/(2 + (k-1)*C).

We care about the sign, so multiply through by the positive quantity (2 + (k-1)*C) * (2 + k*C).

A*C - B*(2 + k*C) = -B*C*k + A*C - 2*B

As long as this quantity is positive, we should increase k. This implies that

k = floor((A*C - 2*B)/(B*C))

upgrades is the optimal solution.

Upvotes: 2

Related Questions