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 I

Number: 3494

Difficulty: Medium

Paid? No

Companies: N/A

Problem Description

Given an m x n cake that must be cut into 1x1 pieces, each possible horizontal and vertical cut has an associated cost. The horizontalCut array provides the cost for each of the m-1 horizontal cuts, and the verticalCut array gives the cost for each of the n-1 vertical cuts. At each step, you can make a cut on any piece that isn’t already a 1x1 square. The cost to cut depends on the line’s inherent cost multiplied by the number of pieces that the cut will affect. Determine the minimum total cost required to cut the entire cake into 1x1 squares.

Key Insights

  • Sort both horizontal and vertical cut cost arrays in descending order.
  • Use a greedy approach: always choose the highest available cost cut first.
  • Maintain counters for the number of current pieces horizontally and vertically.
  • The cost of a horizontal cut is multiplied by the current number of vertical pieces, and vice versa.
  • This strategy minimizes the overall multiplication effect on cuts with high costs.

Space and Time Complexity

Time Complexity: O(m log m + n log n) due to sorting the cut cost arrays.
Space Complexity: O(m + n) as additional space is used for sorting the input arrays.

Solution

We adopt a greedy approach similar to the chocolate cutting problem. First, sort both cut arrays in descending order. Use two pointers for horizontal and vertical cuts. Also, maintain a count of horizontal and vertical pieces (initially 1 each). At every step, choose the cut (horizontal or vertical) with a higher cost. When performing a horizontal cut, multiply its cost by the number of vertical pieces (since the cut spans all vertical pieces) and increase the horizontal piece count. Similarly, for a vertical cut, multiply its cost by the number of horizontal pieces and increase the vertical piece count. If one array is exhausted, process the remaining cuts from the other array accordingly.

Code Solutions

# Python solution for Minimum Cost for Cutting Cake I

def minimum_cake_cut_cost(m, n, horizontalCut, verticalCut):
    # Sort the cost arrays in descending order
    horizontalCut.sort(reverse=True)
    verticalCut.sort(reverse=True)
    
    # Initialize counters for current pieces in each dimension
    horizontalPieces = 1  # Initially one horizontal segment
    verticalPieces = 1    # Initially one vertical segment
    i, j = 0, 0         # Pointers for horizontal and vertical cuts
    total_cost = 0      # Accumulate total cost
    
    # Continue processing until one of the arrays is exhausted
    while i < len(horizontalCut) and j < len(verticalCut):
        # Choose the cut with the higher cost first
        if horizontalCut[i] >= verticalCut[j]:
            # For a horizontal cut, cost impacts all vertical segments
            total_cost += horizontalCut[i] * verticalPieces
            horizontalPieces += 1  # Increase count of horizontal segments
            i += 1
        else:
            # For a vertical cut, cost impacts all horizontal segments
            total_cost += verticalCut[j] * horizontalPieces
            verticalPieces += 1  # Increase count of vertical segments
            j += 1
    
    # Process any remaining horizontal cuts
    while i < len(horizontalCut):
        total_cost += horizontalCut[i] * verticalPieces
        horizontalPieces += 1
        i += 1
    
    # Process any remaining vertical cuts
    while j < len(verticalCut):
        total_cost += verticalCut[j] * horizontalPieces
        verticalPieces += 1
        j += 1
    
    return total_cost

# Example usage:
if __name__ == "__main__":
    m = 3
    n = 2
    horizontalCut = [1, 3]
    verticalCut = [5]
    print(minimum_cake_cut_cost(m, n, horizontalCut, verticalCut))  # Expected output: 13
← Back to All Questions