BAKCOST - Editorial

Contest

DIFFICULTY:

MEDIUM

PROBLEM:

There are NN items in the bakery. Each item’s cost is cost[i]cost[i] and the delivery charge is delivery_cost[i]delivery_cost[i] for ii = 00 to NN respectively. The chef wants to select exactly MM items to sell in a way that the total cost is maximized.

The total cost for any set of items is the sum of costs of those items + (minimum delivery cost among those items * total no. of items). Help the chef find the maximum cost for MM items.

EXPLANATION

There are two major ways to think about this problem. One is a backtracking-based approach and the other is a heap-based approach.

1. Backtracking:

The main idea of this approach is to try all the possibilities using recursion and use memorization to overcome repeated computations.

SOLUTION

import sys
min_d = 10 ** 7

# set recursion limit
sys.setrecursionlimit(10 ** 7)

# argument mid_d_cost maps to the minimum delivery cost
# among the current set of items in the bag.
def recurce(i, bag_size, min_d_cost):
    # base cases
    if bag_size == 0: return min_d_cost * m
    if i >= n: return 0

    if (i, bag_size, min_d_cost) in DP:
        return DP[(i, bag_size, min_d_cost)]
    k = max(
        cost[i] + recurce(i+1, bag_size-1, min(min_d_cost, cost_d[i])),
        recurce(i+1, bag_size, min_d_cost)
    )
    DP[(i, bag_size, min_d_cost)] = k
    return k

t = int(input())
for _ in range(t):
    n, m = map(int, input().split())
    cost = list(map(int, input().split()))
    cost_d = list(map(int, input().split()))
    DP = {}
    print(recurce(0, m, min_d))

Time complexity: O(m * n)
Space Complexity: O(m * n * n)

2. Heap:

Solution author: nihal_47

The idea of this solution is to first sort the data based on delivery costs, Pickup m-1 items with the highest prices using a heap. And then select one item based on delivery cost + price that maximizes the total cost.

SOLUTIONS

import heapq
t = int(input())
for _ in range(t):
    n, m = map(int, input().split())
    li = list(map(int, input().split()))
    data = []
    temp = list(map(int, input().split()))
 
    for i in range(n):
        data.append([temp[i], li[i]])
 
    data.sort(key=lambda x: x[0])
    ans = 0
    psum = [0] * (n+1)
    pq = []
    heapq.heapify(pq)
    sum = 0
    for i in range(n-1, 0, -1):
        if (i >= (n - (m-1))):
            sum += data[i][1]
            psum[i] = sum
            heapq.heappush(pq, data[i][1])
        else:
            heapq.heappush(pq, data[i][1])
            sum += data[i][1]
            sum -= heapq.heappop(pq)
            psum[i] = sum
    for i in range(n):
        if (i+m-1 < n):
            ans = max(ans, data[i][0] * m + (psum[i+1] + data[i][1]))
    print(ans)

Time Complexity: O(n * log n)
Space Complexity: O(n)

Note: The first solution will not pass subtask 2 in the original problem but it was a good approach to know about, hence we decided to include that in the editorial.

Feel free to share other approaches.