Scale Engineer

Minimum Cost for Cutting Cake II

Hard
#2859Time: O((m+n) * 2^(m+n)). There are `2^(m-1) * 2^(n-1)` states, and for each state, we iterate through up to `m-1 + n-1` possible next cuts.Space: O(2^(m+n)). The memoization table requires `2^(m-1) * 2^(n-1)` entries.
Patterns
Greedy
Algorithms
Sorting
Data structures
Array

Prompt

There is an m x n cake that needs to be cut into 1 x 1 pieces.

You are given integers m, n, and two arrays:

  • horizontalCut of size m - 1, where horizontalCut[i] represents the cost to cut along the horizontal line i.
  • verticalCut of size n - 1, where verticalCut[j] represents the cost to cut along the vertical line j.

In one operation, you can choose any piece of cake that is not yet a 1 x 1 square and perform one of the following cuts:

  1. Cut along a horizontal line i at a cost of horizontalCut[i].
  2. Cut along a vertical line j at a cost of verticalCut[j].

After the cut, the piece of cake is divided into two distinct pieces.

The cost of a cut depends only on the initial cost of the line and does not change.

Return the minimum total cost to cut the entire cake into 1 x 1 pieces.

 

Example 1:

Input: m = 3, n = 2, horizontalCut = [1,3], verticalCut = [5]

Output: 13

Explanation:

  • Perform a cut on the vertical line 0 with cost 5, current total cost is 5.
  • Perform a cut on the horizontal line 0 on 3 x 1 subgrid with cost 1.
  • Perform a cut on the horizontal line 0 on 3 x 1 subgrid with cost 1.
  • Perform a cut on the horizontal line 1 on 2 x 1 subgrid with cost 3.
  • Perform a cut on the horizontal line 1 on 2 x 1 subgrid with cost 3.

The total cost is 5 + 1 + 1 + 3 + 3 = 13.

Example 2:

Input: m = 2, n = 2, horizontalCut = [7], verticalCut = [4]

Output: 15

Explanation:

  • Perform a cut on the horizontal line 0 with cost 7.
  • Perform a cut on the vertical line 0 on 1 x 2 subgrid with cost 4.
  • Perform a cut on the vertical line 0 on 1 x 2 subgrid with cost 4.

The total cost is 7 + 4 + 4 = 15.

 

Constraints:

  • 1 <= m, n <= 105
  • horizontalCut.length == m - 1
  • verticalCut.length == n - 1
  • 1 <= horizontalCut[i], verticalCut[i] <= 103

Approaches

3 approaches with complexity analysis and trade-offs.

This approach attempts to solve the problem by exploring every possible sequence of cuts using dynamic programming with bitmasking. A state in our DP is defined by the set of horizontal and vertical cuts that have already been performed. These sets are represented by bitmasks. For each state, we recursively calculate the minimum cost by trying every possible next cut (both horizontal and vertical) and choosing the one that leads to the minimum total cost for the subsequent cuts.

Algorithm

  • Define a recursive function solve(hMask, vMask) with memoization, where hMask and vMask are bitmasks representing the cuts already made.
  • The base case for the recursion is when all cuts have been made (all bits in masks are set), in which case the cost is 0.
  • If the result for a state (hMask, vMask) is already in the memoization table, return it.
  • To compute the cost for a state, initialize a minCost variable to infinity.
  • Determine the current number of horizontal and vertical pieces. The number of horizontal pieces is popcount(hMask) + 1, and vertical pieces is popcount(vMask) + 1.
  • Iterate through all horizontal cuts. If a cut i has not been made yet, calculate the cost of making it now: cost = horizontalCut[i] * (number of vertical pieces) + solve(new_hMask, vMask). Update minCost with this value if it's smaller.
  • Similarly, iterate through all vertical cuts. If a cut j has not been made, calculate its cost: cost = verticalCut[j] * (number of horizontal pieces) + solve(hMask, new_vMask). Update minCost accordingly.
  • Store the computed minCost in the memoization table and return it.
  • The initial call to the function will be solve(0, 0).

Walkthrough

The core of this method is a recursive function, let's call it solve(hMask, vMask), which computes the minimum cost to finish cutting the cake given that the cuts represented by hMask (for horizontal) and vMask (for vertical) are already done. The cost of making a new cut depends on the number of pieces it must slice through. A horizontal cut slices through a number of pieces equal to the current number of vertical segments (popcount(vMask) + 1). A vertical cut slices through a number of pieces equal to the current number of horizontal segments (popcount(hMask) + 1). The function explores making each available cut, recursively calls itself for the new state, and takes the minimum over all possibilities. Memoization is used to store the results for each (hMask, vMask) pair to avoid redundant computations. However, due to the 2^(m-1) * 2^(n-1) possible states, this approach is not feasible for the problem's constraints.

// This is a conceptual implementation and will time out for the given constraints.import java.util.Arrays; class Solution {    private long[][] memo;    private int m, n;    private int[] horizontalCut, verticalCut;    private int hTargetMask, vTargetMask;     public long minimumCost(int m, int n, int[] horizontalCut, int[] verticalCut) {        // This approach is too slow for the given constraints but illustrates the concept.        if (m > 15 || n > 15) return -1; // Heuristic check to prevent memory errors        this.m = m;        this.n = n;        this.horizontalCut = horizontalCut;        this.verticalCut = verticalCut;        this.hTargetMask = (1 << (m - 1)) - 1;        this.vTargetMask = (1 << (n - 1)) - 1;        this.memo = new long[1 << (m - 1)][1 << (n - 1)];        for (long[] row : memo) {            Arrays.fill(row, -1);        }        return solve(0, 0);    }     private long solve(int hMask, int vMask) {        if (hMask == hTargetMask && vMask == vTargetMask) {            return 0;        }        if (memo[hMask][vMask] != -1) {            return memo[hMask][vMask];        }         long minCost = Long.MAX_VALUE;        int hPieces = Integer.bitCount(hMask) + 1;        int vPieces = Integer.bitCount(vMask) + 1;         // Try making a horizontal cut        if (hMask != hTargetMask) {            for (int i = 0; i < m - 1; i++) {                if ((hMask & (1 << i)) == 0) {                    long currentCost = (long) horizontalCut[i] * vPieces + solve(hMask | (1 << i), vMask);                    minCost = Math.min(minCost, currentCost);                }            }        }         // Try making a vertical cut        if (vMask != vTargetMask) {            for (int i = 0; i < n - 1; i++) {                if ((vMask & (1 << i)) == 0) {                    long currentCost = (long) verticalCut[i] * hPieces + solve(hMask, vMask | (1 << i));                    minCost = Math.min(minCost, currentCost);                }            }        }         return memo[hMask][vMask] = minCost;    }}

Complexity

Time

O((m+n) * 2^(m+n)). There are `2^(m-1) * 2^(n-1)` states, and for each state, we iterate through up to `m-1 + n-1` possible next cuts.

Space

O(2^(m+n)). The memoization table requires `2^(m-1) * 2^(n-1)` entries.

Trade-offs

Pros

  • It is a correct approach that is guaranteed to find the optimal solution by exhaustively checking all possibilities.

Cons

  • Extremely high time and space complexity, making it impractical for the given constraints.

  • The state space grows exponentially with m and n, leading to Time Limit Exceeded (TLE) or Memory Limit Exceeded (MLE) errors for anything but very small inputs.

Solutions

class Solution {public  long minimumCost(int m, int n, int[] horizontalCut, int[] verticalCut) {    Arrays.sort(horizontalCut);    Arrays.sort(verticalCut);    long ans = 0;    int i = m - 2, j = n - 2;    int h = 1, v = 1;    while (i >= 0 || j >= 0) {      if (j < 0 || (i >= 0 && horizontalCut[i] > verticalCut[j])) {        ans += 1L * horizontalCut[i--] * v;        ++h;      } else {        ans += 1L * verticalCut[j--] * h;        ++v;      }    }    return ans;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem