Discussion on Making Candies Challenge

2 months ago+ 0 comments

Intuition & Approach:

We can try all possible round numbers and see if we can make candies in each required number of rounds, however, we notice that if we can produce candies in x rounds then any number of rounds greater than x is redundant to check. SO we can try a round and if we can make the required number of candies we can try for a smaller number of rounds, if we cant then we should try for a higher number of rounds ... this is a binary search! Don’t worry if you didn’t figure that out, recognising this comes with practise.

The check function is a bit complicated since you have to simulate producing candies and trying out purchasing more workers but this can be done if we always check that the current workers and machines setup can reach the required candies before trying to buy an additional worker or machine (which can be done optimally by trying to keep them the same), after which we check again if that setup produces enough for the solution within the rounds and so on. IF we can’t purchase new workers/machines then we have to wait a certain number of rounds (while still producing candies) so we keep checking if we’re reached the target number of candies but if we run out of rounds at any point we return False.

By carefully implementing the check function, this question becomes fairly straightforward! spend time understanding the check function for yourself and what each section is doing to solidify your understanding.

Implementation

def checkIfMidPassesPossible(machines, workers, price, target, rounds):
    # Immediately return if we can produce enough in one round
    if machines * workers >= target:
        return True

    # We maintaing the candies we currently have and the rounds we have left
    current_candies = machines * workers
    rounds -= 1

    # We go till we have enough rounds to do produce (and potentially purchase in)
    while rounds > 0:
        # STEP 1) Check if we can reach the end w/ the current production rate
        remaining_candies = target - current_candies
        
        needed_rounds = (remaining_candies) // (machines * workers)
        if remaining_candies % (machines * workers) > 0:
            needed_rounds += 1  # To round up for day with partial production

        if needed_rounds <= rounds:
            return True
        
        # STEP 2) Wait until we have enough to purchase a worker and return False
        # if we need to wait too long
        if current_candies < price:
            additional_needed = price - current_candies
            rounds_needed_to_buy = additional_needed // (machines * workers)
            
            if additional_needed % (machines * workers) > 0:
                rounds_needed_to_buy += 1
            rounds -= rounds_needed_to_buy  # MAINTAIN ROUNDS LEFT

            if rounds <= 0:
                return False
            
            current_candies += rounds_needed_to_buy * machines * workers    # MAINTAIN CANDIES PRODUCED

        # STEP 3) Make the optimal purchase of worker or machine
        current_candies -= price    # MAINTAIN CANDIES PRODUCED
        machines, workers = (machines + 1, workers) if machines <= workers else (machines, workers + 1)
        
    # If we run out of rounds, we haven't reached the target and there aren't any more round
    return False

def minimumPasses(m, w, p, n):
    low, high = 1, 10**12  # Set a large upper bound, we set low to 1 since we never start
    # with any candies

    while low < high:
        mid = (low + high) // 2
        if checkIfMidPassesPossible(m, w, p, n, mid):
            high = mid  # Look for fewer passes
        else:
            low = mid + 1  # Increase passes

    return low

Intuition & Approach:

Implementation

Cookie support is required to access HackerRank