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 Cost for Cutting Cake II

Number: 3500

Difficulty: Hard

Paid? No

Companies: N/A

Problem Description

Given an m x n cake, you need to cut it into individual 1 x 1 pieces. There are two arrays—horizontalCut and verticalCut—that provide the cost to cut along each horizontal or vertical line respectively. In one operation, you choose any cake piece that isn’t 1 x 1 and perform a horizontal cut (cost from horizontalCut) or a vertical cut (cost from verticalCut). The cost of each cut is fixed (given in the arrays), but note that a cut might affect multiple pieces later on. The goal is to compute the minimum total cost to divide the entire cake into 1 x 1 pieces.

Key Insights

  • This problem is analogous to the "Cutting Board" or "Cutting Bars" problem where you need to minimize the cost by choosing the order of cuts wisely.
  • A greedy strategy works best: sort both the horizontal and vertical cut costs in descending order.
  • At every step, choose the cut with the highest cost. However, note that a horizontal cut will affect all current vertical segments and vice versa.
  • Maintain counters:
    • horizontalParts (initially 1) representing the current pieces vertically.
    • verticalParts (initially 1) representing the current pieces horizontally.
  • When performing a horizontal cut, the cost incurred is the cut’s cost multiplied by the number of vertical pieces; similarly, a vertical cut multiplies its cost by the number of horizontal pieces.
  • Continue the process until all cut costs have been used. If one array is exhausted, process the remaining cuts from the other array accordingly.

Space and Time Complexity

Time Complexity: O((m+n) log(m+n)) — primarily due to sorting the two arrays. Space Complexity: O(m+n) — used for storing the sorted arrays and constant extra space for counters.

Solution

The solution uses a greedy algorithm. First, sort both horizontalCut and verticalCut arrays in descending order. Use two counters, horizontalParts and verticalParts, to record how many pieces are formed in the perpendicular direction after previous cuts. Process the cuts in order of descending cost. If the next highest cost is from a horizontal cut, add cost * verticalParts to the total cost and increase horizontalParts by one; if it is vertical, add cost * horizontalParts and increase verticalParts by one. Continue until all cuts have been made. This strategy ensures that the high-cost cuts are applied with the minimum multiplier, leading to the minimum overall cost.

Code Solutions

# Python solution using a greedy approach

def minimumCost(m, n, horizontalCut, verticalCut):
    # Sort both lists in descending order
    horizontalCut.sort(reverse=True)
    verticalCut.sort(reverse=True)
    
    # Initialize counters for pieces created by cuts
    horizontalPieces = 1   # Initially one vertical piece (no horizontal cuts made)
    verticalPieces = 1     # Initially one horizontal piece (no vertical cuts made)
    
    total_cost = 0
    h = 0  # pointer for horizontalCut
    v = 0  # pointer for verticalCut
    
    # Process cuts until either list is exhausted
    while h < len(horizontalCut) and v < len(verticalCut):
        # If next horizontal cut cost is greater than vertical, pick horizontal cut
        if horizontalCut[h] >= verticalCut[v]:
            total_cost += horizontalCut[h] * verticalPieces
            horizontalPieces += 1
            h += 1
        else:
            total_cost += verticalCut[v] * horizontalPieces
            verticalPieces += 1
            v += 1
    
    # Process any remaining horizontal cuts
    while h < len(horizontalCut):
        total_cost += horizontalCut[h] * verticalPieces
        horizontalPieces += 1
        h += 1
    
    # Process any remaining vertical cuts
    while v < len(verticalCut):
        total_cost += verticalCut[v] * horizontalPieces
        verticalPieces += 1
        v += 1
    
    return total_cost

# Example usage:
print(minimumCost(3, 2, [1,3], [5]))  # Output: 13
← Back to All Questions