Sort 119 Discussions, By:
Please Login in order to post a comment
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.
Is there a proof that we must only buy-all or buy-none? Why is buy-some not optimal?
Here are some hints and observations that should help solve this problem:
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
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?
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++.