# Making Candies - HackerRank question - proof of optimality of a greedy approach

I stumbled across this question in HackerRank:

Karl loves playing games on social networking sites. His current favorite is CandyMaker, where the goal is to make candies. Karl just started a level in which he must accumulate $$n$$ candies starting with $$m$$ machines and $$w$$ workers. In a single pass, he can make $$m \times w$$ candies. After each pass, he can decide whether to spend some of his candies to buy more machines or hire more workers. Buying a machine or hiring a worker costs $$p$$ units, and there is no limit to the number of machines he can own or workers he can employ.

Karl wants to minimize the number of passes to obtain the required number of candies at the end of a day. Determine that number of passes.

For example, Karl starts with $$m=1$$ machine and $$w=2$$ workers. The cost to purchase or hire, $$p=1$$ and he needs to accumulate $$60$$ candies. He executes the following strategy:

Make $$m \times w = 2$$ candies. Purchase two machines.

Make $$3 \times 2 = 6$$ candies. Purchase $$3$$ machines and hire $$3$$ workers.

Make $$6 \times 5 = 30$$ candies. Retain all $$30$$ candies.

Make $$30$$ candies. With yesterday's production, Karl has $$60$$ candies. It took $$4$$ passes to make enough candies.

The hypothesis is that the greedy approach, where we always spend as much money as possible to purchase workers/machines (until the last pass where we wait one more time to gather enough candies) is the optimal one. If this is the case - why?

• The first question should be whether the greedy approach always works. Does it work if m = 3, w=3, p = 9, n = 27? – John L. Feb 1 at 15:40
• Thanks @john-l Fair. What about the statement: The optimal strategy is to, at each step, either buy as much as possible or buy none. How would I go about proving/disproving this? – Tomasz Bartkowiak Feb 1 at 18:02
• @TomaszBartkowiak The optimal strategy is as you just said, but even more, all the purchases take place as early as possible. You can prove it with an exchange argument, loosely: if strategy S involves buying $m_i, w_i$ machines and workers at pass $i$, then compare it to strategy S' which makes all the same purchases, but changes one purchase to be earlier if possible. S and S' have the same deductions, but the single earlier purchase in S' means that the gains are higher. – Matthew C Feb 2 at 1:16
• To schedule the purchases correctly will use one more fact that subject to constant $i+j$, $i*j$ is maximized when both are equal or close to equal – Matthew C Feb 2 at 1:18
• This looks like slavery. Normally you don't pay for hiring workers, but for them working. – gnasher729 Feb 2 at 18:04