### Aspergillus's blog

By Aspergillus, history, 7 weeks ago,

The other day someone asked a problem: where we are mining x amount of gold at the end of each day, and the collected gold can be used to buy some extra machines which in turn helps us dig more gold, the machines cost some amount of money each, but their production rate is same (= z). We want maximum gold at the end of the $K^{th}$ day This problem was pretty simple because the production rate was the same for all the machines.

My question is, if the production rate was different, then which machine would have been the optimal choice at the start of each day? This question can be reduced to the following: Consider an array: $a_1(K - i) - b_1, a_2(K - i) - b_2, \ldots, a_n(K - i) - b_n$, where $a_k$ is the production rate of the $k^{th}$ machine, $b_k$ is the cost of the $k^{th}$ machine, and $i$ is the $0-indexed$ day, changing which I want to observe the order of the elements. Here, each element of the array represent how much each machine will contribute to the total gold if it's bought at the start of the $i^{th}$ day. Now, slightly deviating from the original problem and ignoring that one machine can be bought only once, is there a way to find the maximum element for each $i$, from $0$ to $K - 1$ with $K \leq 10^5$?

• -3