We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Search
  4. Making Candies
  5. Discussions

Making Candies

Sort by

recency

|

138 Discussions

|

  • arsnfld
     + 0 comments

    Is the assumption that you should buy production resources every time correct? Assume m=1, w=1, p=100, n=101 After 100 rounds we have 100 candies. If we run just one more round we can get to 101 If we "invest" these 100, then at the 101st round we only have 2 candies. What am I missing?

  • lehuyduc
     + 0 comments

    Many accepted submissions (that use greedy algo) are actually wrong.

    Need to add these tests: ` Input: 5 5 25 50 Output: 2 And Input: 5 5 1 100 Output: 2

  • lehuyduc
     + 0 comments

    Many accepted submissions (that use greedy algo) are actually wrong. Need to add these tests: ` Input: 5 5 25 50 Output: 2 And Input: 5 5 1 100 Output: 2

  • 1337er
     + 0 comments

    Time Complexity O(log n) Space Complexity O(1)

    from math import ceil

def minimumPasses(m, w, p, n):
    min_turns = ceil(n/(m*w))  # min turns without ever buying more workers or machines
    if p > n:
        return min_turns
    turn = 0
    candies = 0
    while candies < n:
        # skip to next turn with buying opportunity
        skip_turns = max([ceil((p - candies) / (m*w)), 1])
        turn += skip_turns
        if turn > min_turns:
            # no reason to continue buying the best strategy is to just save from last min_turn calc
            return min_turns
        candies += m*w * skip_turns
        if candies >= p:
            # get new machines
            new_machines = candies // p
            candies -= new_machines * p
            diff = m-w
            # try to balance workers and machines
            if diff > 0:
                w_buy = min(new_machines, diff)
                w += w_buy
                new_machines -= w_buy
            else:
                m_buy = min(new_machines, abs(diff))
                m += m_buy
                new_machines -= m_buy
            # split remainder after balancing and buy half workers and half machines
            w_buy = new_machines // 2
            w += w_buy
            m += new_machines - w_buy
        # check how long till goal without buying anything
        min_turns = min(ceil((n-candies)/(m*w))+turn, min_turns)
    return turn

  • vivianlopez777
     + 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