Katkat
Back

Minimize total factory cost with distance penalties

StripeSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to use dynamic programming to minimize a total cost function that incorporates both intrinsic production costs and location-based transition penalties.

Problem Statement

You are tasked with building a series of products across a sequence of $N$ factories. Each factory $i$ (where $0 <= i < N$) has a fixed production cost costs[i]. Additionally, there is a location-based penalty: if you build in factory $i$ and then immediately build the next product in factory $j$, you incur a penalty equal to abs(i - j) * K, where $K$ is a constant.

You must build exactly $M$ products, choosing one factory for each product. Each factory can be used at most once. Your goal is to minimize the total cost (sum of costs of chosen factories + sum of penalties between consecutive choices).

Function Signature

def min_factory_cost(costs: List[int], M: int, K: int) -> int:

Constraints

  • 1 = 0
  • 0 <= K <= 1000

Examples

Example 1: Input: costs = [10, 20, 30], M = 2, K = 5 Output: 35 Explanation: Pick factories 0 and 2 (costs 10 + 30). Penalty is abs(0 - 2) * 5 = 10. Total: 50. Pick factories 0 and 1 (costs 10 + 20). Penalty abs(0 - 1) * 5 = 5. Total: 35. Minimum is 35.

Example 2: Input: costs = [5, 1, 5], M = 2, K = 100 Output: 6 Explanation: Pick factories 0 and 1. Cost 5+1 + abs(0-1)*100 = 106. Pick factories 1 and 2. Cost 1+5 + abs(1-2)*100 = 106. Pick factories 0 and 2. Cost 5+5 + abs(0-2)*100 = 210. Wait, actually, the best is 0 and 1 (6) or 1 and 2 (6).

Hints

Hint 1

Define a DP state as `dp(count, last_index)` representing the minimum cost to complete the remaining products given the index of the previously used factory.

Hint 2

The transition involves iterating through all possible indices `j > last_index` for the next factory, calculating `costs[j] + (j - last_index) * K`.

Hint 3

Since the choice of factory $i$ for the first product has no penalty, handle the first selection as a base case or use a dummy index.

Follow-up questions

  • How would the solution change if you were allowed to build multiple products at the same factory for a different cost penalty?
  • What is the time complexity of your approach, and could you optimize it if $N$ were much larger but $K$ was 0?
  • If the factory sequence was circular (i.e., you can move from factory $N-1$ back to $0$), how would you adjust the penalty calculation?