- Prepare
- Algorithms
- Search
- Making Candies
- Discussions

# Making Candies

# Making Candies

+ 0 comments This problem is worded poorly. The objective is stated: Can you find and print the minimum number of passes required for Karl to make at least n units of candies?

Making the candies implies m*w >= n Instead, according to the test cases, it appears the real question is to find the minimum number of passes for Karl to HAVE n units of candies in his possession.

Someone correct me if I am wrong, but I do not see how Test Case #1 can "make" 45 units in 16 passes. 17 passes are required to produce >= 45 units. Karl can have 45 units in his possession after 16 passes if none are spent in the previous pass.

+ 0 comments Is there a proof that we must only buy-all or buy-none? Why is buy-some not optimal?

+ 0 comments Here are some hints and observations that should help solve this problem:

- There are two strategies, "invest" and "save". "Invest" means we're buying as many machines/workers as possible as soon as we can, "save" means we just keep accumulating candies every turn without investing.
- For a single round of investing, it is optimal to make purchases such that after the purchase, the number of machines is as close to the number of workers as possible. Example: 5*5 > 4*6 > 3*7 etc.
- The optimal overall strategy will consist of an investing phase at the beginning, and at some point to stop investing and transition into a saving phase. It is not obvious where this crossover point is. It should be obvious that going back and forth between saving and investing is never optimal. Less obvious is that if we're investing, we're investing as much as possible in a single round. I haven't been able to construct an example where it is better to partially invest and save in a single round, but haven't worked out a formal proof.
- In the "invest" phase, the candy production will grow exponentially, which means iterating over all turns where we can invest should be efficient enough. This will require to "skip" turns where we can't invest, if p is a large value. This can be done with simple arithmetic in constant time.
- After every investment, we can calculate how many turns already elapsed plus how many turns of saving it will take to reach our goal. We keep a running minimum of this number, and this will be the end result. Since this number can be calculated arithmetically in constant time, our algorithm will run in logarithmic time (or in fractional power power time, haven't exactly figured this out).
- We can terminate when we have accumulated enough machines/workers to produce >= n candies in one turn, and return the running minimum we determined above.

+ 0 comments My solution in python

def minimumPasses(m, w, p, n): candy = 0 invest = 0 spend = sys.maxsize while candy < n: passes = (p - candy) // (m * w) if passes <= 0: mw = (candy // p) + m + w half = math.ceil(mw / 2) if m > w: m = max(m, half) w = mw - m else: w = max(w, half) m = mw - w candy %= p passes = 1 candy += passes * m * w invest += passes spend = min(spend, invest + math.ceil((n - candy) / (m * w))) return min(invest, spend)

Not sure how you'd even incorporate binary search here?

+ 0 comments For those of you struggling, consider a greedy approach where you always buy resources when possible, and check for that number of resources how many more iterations it would take to exceed n from the current point. This is O(n) but you can build shortcuts into the code by noting that whenever you dont have enough funds to afford resources, you can "skip" to the next point at which you can and increment the rounds accordingly. This approach passes all test cases. Watch out for overflow too and make everything unsigned long long if you're in C++.

Sort 119 Discussions, By:

Please Login in order to post a comment