Making Candies

Sort by

recency

|

135 Discussions

|

  • + 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
    
  • + 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
    
  • + 0 comments

    100% Javascript solution that should be easy to understand

    function minimumPasses(m, w, p, n) {
        if (n <= p) {
            return Math.ceil(n / (m * w));
        }
        
        let currentDay = 0;
        let candy = 0;
        
        while (candy < n) {
            const remainingDaysWithCurrentProduction = Math.ceil((n - candy) / (m * w));      
            
            const canBuy = Math.floor(candy / p);
            
            if (canBuy === 0) {
                // keep saving until enough for a purchase            
                const i = Math.ceil((p - candy) / (m * w));
                currentDay += i;
                candy += (m * w * i);
                continue;
            }
    
            const total = m + w + canBuy;
            const half = Math.floor(total / 2);
            let mNew = m;
            let wNew = w;
    
            if (m > w){
                mNew = Math.max(m, half);
                wNew = total - mNew;
            } else {
                wNew = Math.max(w, half);
                mNew = total - wNew;
            }
            
            const rest = candy % p;
            const remainingDaysWithIncreasedProduction = Math.ceil((n - rest) / (mNew * wNew));
            
            if (remainingDaysWithCurrentProduction < remainingDaysWithIncreasedProduction) {
                // stop purchasing and produce until done
                return currentDay + remainingDaysWithCurrentProduction;
            }
            
            // purchases machines and workers and continue
            candy = rest;
            m = mNew;
            w = wNew;            
            currentDay += 1;
            candy += (m * w);
        }
        
        return currentDay;
    }
    
  • + 0 comments

    Can I make greater than or equal to required candies or it should be exactly n ??

  • + 0 comments
    import math
    import os
    
    def minimumPasses(m, w, p, n):
        if n <= p: return math.ceil(n / (m * w))
    
        curr = candy = 0
        ans = float('inf')
    
        while candy < n:
            if candy < p:
                i = math.ceil((p - candy) / (m * w))
                curr += i
                candy += m * w * i
                continue
    
            buy,candy = divmod(candy , p)
            total = m + w + buy
            half = total // 2
    
            if m > w :
                m = max(m, half)
                w = total - m
            else:
                w = max(w, half)
                m = total - w
    
            curr += 1
            candy += m * w
            ans = min(ans, curr + math.ceil((n - candy) / (m * w)))
    
        return min(ans, curr)
    
    
    if __name__ == '__main__':
        fptr = open(os.environ['OUTPUT_PATH'], 'w')
    
        mwpn = input().split()
    
        m = int(mwpn[0])
        w = int(mwpn[1])
        p = int(mwpn[2])
        n = int(mwpn[3])
    
        result = minimumPasses(m, w, p, n)
    
        fptr.write(str(result))
        fptr.close()