We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Relative Loss After Buying Chocolates

Number: 3077

Difficulty: Hard

Paid? Yes

Companies: N/A

Problem Description

Given an array of chocolate prices and a list of queries, each query provides a number k and an integer m. Under the payment rules – if a chocolate’s price is ≤ k then Bob pays its full price; if it’s > k then Bob pays only k and Alice covers the remainder – Bob must choose exactly m chocolates so that his “relative loss” (his total payment minus Alice’s total payment) is minimized. The task is to compute, for each query, the minimum possible relative loss.

Key Insights

  • The payment for each chocolate is defined piece‐wise:
    • If price p ≤ k, loss = p.
    • If price p > k, loss = 2k – p.
  • For a fixed query, each chocolate has an “effective loss” value that depends on k.
  • Notice that expensive chocolates (with p > k) can yield a negative loss (if p is large enough) and are “better” when chosen.
  • If we split the chocolates into two groups – those with p ≤ k (loss = p) and those with p > k (loss = 2k – p) – then within each group the best choices can be taken in order (lowest for the low group; highest prices yield the smallest loss in the high group).
  • The optimal selection among the m chocolates is equivalent to merging two sorted lists (one sorted ascending by p, and one sorted descending by price for p > k) and choosing the m items with smallest effective loss.
  • By defining “x” as the number of chocolates chosen from the high group, the total loss can be written in closed‐form in terms of prefix sums. Then the goal becomes to choose an “x” (subject to feasibility) that minimizes the cost function.
  • The cost function is given by:   cost(x) = 2k * x – (sum of the x highest prices among those > k) + (sum of the (m – x) smallest prices among those ≤ k).
  • Using a global sorted array and its prefix–sum we can quickly compute both candidate sums.
  • The valid range for x is [max(0, m – count_low), min(m, count_high)] (where count_low is the number of prices ≤ k and count_high = n – count_low).
  • Although the function is discrete, its “difference” (or derivative) can be written as d(x) = 2k – A[n – x – 1] – A[m – x – 1] (with A being the global sorted array); this helps in “binary searching” for the turning point.

Space and Time Complexity

Time Complexity: O(n log n + q (log n + log m))
 • O(n log n) for sorting and building prefix sums
 • Each query is processed in O(log n + log m)
Space Complexity: O(n)
 • Storing sorted prices and prefix sums

Solution

The idea is to pre-sort the prices in ascending order and build a prefix–sum array (with prefix[0] = 0 and prefix[i] the sum of the first i prices). For a given query with parameters k and m, we first determine the partition point pos (using binary search) so that all prices with index < pos are ≤ k and those from pos onward are > k. Let count_low = pos and count_high = n – pos.

We then define x as the number of chocolates selected from the high group. Because we must choose exactly m chocolates, the number selected from the low group is (m – x). Feasibility requires (m – x) ≤ count_low and x ≤ count_high so that x lies in:   x ∈ [L, R] where L = max(0, m – count_low) and R = min(m, count_high).

The cost (or total “relative loss”) for a given x is computed by:   cost(x) = 2k * x – (sum of the x largest prices in the high group) + (sum of the (m – x) smallest prices in the low group).

Since the high group is the part A[pos…n–1] of our global sorted array (A sorted in ascending order), the x “best” (i.e. with smallest effective loss) are the x largest among them (located at indices from n – x to n – 1). Their sum is computed using the prefix sum array as:   sum_high = prefix[n] – prefix[n – x].

Similarly, the (m – x) smallest low-group elements are exactly A[0 … (m – x – 1)] (provided (m – x) ≤ count_low) with sum = prefix[m – x].

Thus, we get:   cost(x) = 2k*x – (prefix[n] – prefix[n – x]) + prefix[m – x].

To optimize the total cost, we need to find the x in [L, R] that minimizes cost(x). Although one could try all x values, the valid range could be large. Instead, we examine the “difference” between successive values of x. It can be shown that (for valid indices) the difference:   d(x) = cost(x+1) – cost(x) = 2k – A[n – x – 1] – A[m – x – 1] is monotonic in x. We can thus binary–search the valid x interval to find the turning point where d(x) changes from negative to non–negative. Finally, we check the candidate and nearby boundaries (including the endpoints L and R) to determine the minimum cost.

We then output the resulting cost as Bob’s minimum possible relative loss for that query.

Code Solutions

# Python solution with line-by-line comments

def min_relative_loss(prices, queries):
    # sort prices in ascending order and build prefix sum array
    n = len(prices)
    prices.sort()
    prefix = [0] * (n+1)
    for i in range(1, n+1):
        prefix[i] = prefix[i-1] + prices[i-1]
    
    import bisect
    res = []
    for k, m in queries:
        # Use bisect_right to find first index where price > k
        pos = bisect.bisect_right(prices, k)
        count_low = pos           # prices[0:pos] are <= k
        count_high = n - pos      # prices[pos:n] are > k
        
        # valid x (number chosen from high group) must satisfy:
        # m - x <= count_low  ==> x >= m - count_low
        # and x <= count_high and also x <= m.
        L = max(0, m - count_low)
        R = min(m, count_high)
        
        # Helper function: compute cost for a given x 
        def cost(x):
            # cost = 2k * x - (sum of x largest from high group) + (sum of (m-x) smallest from low group)
            # x largest from high group are at indices from n-x to n-1.
            sum_high = prefix[n] - prefix[n - x] if x > 0 else 0
            sum_low = prefix[m - x] if m - x > 0 else 0
            return 2 * k * x - sum_high + sum_low

        best = None
        
        # If the feasible interval is a single value, use it directly.
        if L == R:
            best = cost(L)
        else:
            # Helper function: difference when increasing x by 1:
            # d(x) = cost(x+1) - cost(x) = 2k - A[n - x - 1] - A[m - x - 1]
            # d(x) can only be computed when (m - x) >= 1.
            def diff(x):
                # if (m - x) == 0, derivative is not defined; we return a very large value.
                if m - x == 0:
                    return float('inf')
                # A[n - x - 1]: get the smallest among chosen high-group candidate (largest first)
                high_term = prices[n - x - 1] if x < count_high else float('inf')
                # A[m - x - 1]: last element among the (m-x) chosen low-group items
                low_term = prices[m - x - 1] if m - x - 1 >= 0 else float('inf')
                return 2 * k - high_term - low_term
            
            # Binary search the interval [L, R) for the first x where diff(x) >= 0
            lo, hi = L, R
            candidate = None
            while lo < hi:
                mid = (lo + hi) // 2
                if m - mid == 0:  
                    # if no low group is chosen, push right
                    lo = mid + 1
                else:
                    if diff(mid) < 0:
                        lo = mid + 1
                    else:
                        hi = mid
            candidate = lo
            
            # Check candidate and nearby possibilities; check boundaries L and R as well.
            possible = set()
            for x in [candidate-1, candidate, candidate+1, L, R]:
                if x is not None and L <= x <= R:
                    possible.add(x)
            best = min(cost(x) for x in possible)
        res.append(best)
    return res

# Example usage:
prices1 = [1,9,22,10,19]
queries1 = [[18,4],[5,2]]
print(min_relative_loss(prices1, queries1))  # Expected: [34, -21]
← Back to All Questions