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

Number of Ways of Cutting a Pizza

Number: 1555

Difficulty: Hard

Paid? No

Companies: Google

Problem Description

Given a rectangular pizza represented as a rows x cols matrix where each cell is either 'A' (an apple) or '.' (empty), and an integer k, we need to cut the pizza into k pieces using k-1 cuts. Each cut can be horizontal or vertical. When making a cut, the piece that is separated (top piece for horizontal, left piece for vertical) is given away. The final remaining piece is given to the last person. The goal is to count the number of ways to make the cuts such that every piece contains at least one apple. The answer should be returned modulo 10^9 + 7.

Key Insights

  • Use a dynamic programming (DP) approach to recursively decide where to make cuts.
  • Precompute a suffix sum (or prefix sum) matrix to quickly determine if a submatrix contains at least one apple.
  • Define dp(row, col, cutRemaining) as the number of ways to cut the sub-pizza starting from (row, col) with the given number of cuts left.
  • When no cuts are left, check whether the remaining submatrix contains at least one apple.
  • Explore both horizontal and vertical cuts only if the piece that is cut off contains at least one apple.
  • Use memoization to avoid recalculating overlapping subproblems.

Space and Time Complexity

Time Complexity: O(k * rows * cols * (rows + cols)) Space Complexity: O(rows * cols * k)

Solution

To solve this problem, we:

  1. Precompute a suffix sum matrix where each cell (i, j) stores the number of apples in the submatrix starting at (i, j) to the bottom-right. This allows O(1) checks for the presence of an apple in any submatrix.
  2. Use a recursive DP function with memoization, dp(i, j, cutsLeft), which returns the number of ways to cut the pizza starting from cell (i, j) using the remaining cuts.
  3. For each state, if cutsLeft is 0, the function returns 1 if there is at least one apple in the remaining submatrix and 0 otherwise.
  4. For each potential horizontal cut (from i+1 to number of rows - 1), if the top submatrix contains an apple, then recursively count the ways for the bottom submatrix.
  5. Similarly, for each vertical cut (from j+1 to number of columns - 1), if the left submatrix contains an apple, then recursively count the ways for the right submatrix.
  6. Sum up all valid ways while taking modulo 10^9 + 7 and store the result in the memoization table to avoid re-computation.
  7. Finally, return the number of ways starting from (0, 0) with k-1 cuts remaining.

Code Solutions

MOD = 10**9 + 7

def ways(pizza, k):
    rows, cols = len(pizza), len(pizza[0])
    
    # Precompute suffix sum: apples[i][j] gives number of apples in pizza[i:][j:]
    apples = [[0]*(cols+1) for _ in range(rows+1)]
    for i in range(rows-1, -1, -1):
        for j in range(cols-1, -1, -1):
            apples[i][j] = (1 if pizza[i][j] == 'A' else 0) \
                           + apples[i+1][j] + apples[i][j+1] - apples[i+1][j+1]
    
    memo = {}
    
    def dp(i, j, cuts):
        # If there are no cuts left, check if remaining pizza has at least one apple
        if cuts == 0:
            return 1 if apples[i][j] > 0 else 0
        
        # Use memoization to avoid recalculations
        if (i, j, cuts) in memo:
            return memo[(i, j, cuts)]
            
        ways_to_cut = 0
        
        # Try horizontal cuts
        for next_i in range(i+1, rows):
            # If the top submatrix has at least one apple, then proceed with the bottom part
            if apples[i][j] - apples[next_i][j] > 0:
                ways_to_cut = (ways_to_cut + dp(next_i, j, cuts - 1)) % MOD
        
        # Try vertical cuts
        for next_j in range(j+1, cols):
            # If the left submatrix has at least one apple, then proceed with the right part
            if apples[i][j] - apples[i][next_j] > 0:
                ways_to_cut = (ways_to_cut + dp(i, next_j, cuts - 1)) % MOD
        
        memo[(i, j, cuts)] = ways_to_cut
        return ways_to_cut
    
    return dp(0, 0, k-1)

# Example usage:
pizza = ["A..", "AAA", "..."]
k = 3
print(ways(pizza, k))
← Back to All Questions