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

Pizza With 3n Slices

Number: 1489

Difficulty: Hard

Paid? No

Companies: Google

Problem Description

Given an array of pizza slice sizes arranged in a circle with exactly 3n slices, you must pick n slices (one per turn) to maximize the sum of sizes. However, every time you pick a slice, your two friends immediately pick the slices adjacent to your pick (one in the anti-clockwise direction and one in the clockwise direction). Consequently, the slices you ultimately choose cannot be adjacent in the circular arrangement. The goal is to find the maximum possible sum of the n slices you can pick.

Key Insights

  • The problem is equivalent to choosing n non-adjacent slices from 3n slices arranged in a circle.
  • Because of the circular structure, selecting the first slice affects the possibility of selecting the last slice. Therefore, we break the problem into two cases: (1) consider slices from index 0 to L-2, and (2) consider slices from index 1 to L-1.
  • Dynamic programming is used by defining dp[i][j] as the maximum sum achievable from the first i slices when picking j slices with the non-adjacency constraint.
  • A recurrence relation is built as: dp[i][j] = max(dp[i-1][j], dp[i-2][j-1] + slices[i]) (adjust indices accordingly and ensure proper base conditions).
  • The final answer is the maximum of the results from the two cases.

Space and Time Complexity

Time Complexity: O(n * m) where m is the number of slices in each considered range. Since m is O(3n), this becomes O(n^2). Space Complexity: O(n * m) which is also O(n^2).

Solution

We solve the problem using dynamic programming. The main idea is to convert the picking process into a DP selection problem where we want to choose n slices such that no two chosen slices are adjacent. However, because the slices are arranged in a circle, we have to split the problem into two scenarios: one excluding the last slice and the other excluding the first slice. For each scenario, we run a DP where:

  • dp[i][j] represents the maximum sum when considering up to the i-th slice and picking j slices.
  • When considering a slice at index i, if we decide to pick it then we add its value to the result from dp[i-2][j-1] (since we cannot pick the adjacent slice), otherwise we skip it and take dp[i-1][j].
  • Finally, we take the maximum of the two scenarios as our answer.

Code Solutions

# Python solution
def maxSizeSlices(slices):
    # Helper function for DP on a linear (non-circular) subarray of slices.
    def max_slices(arr):
        n = len(arr)
        picks = len(slices) // 3  # n = total slices / 3
        # Initialize DP table with dimensions (n+2) x (picks+1)
        dp = [[0] * (picks + 1) for _ in range(n + 2)]
        # dp table: dp[i][j] means maximum sum with j picks using first i elements of arr
        for i in range(2, n + 2):
            for j in range(1, picks + 1):
                # Do not take current slice, so use previous state (i-1)
                not_take = dp[i - 1][j]
                # Take current slice (which is at index i-2 in arr) and add it to dp[i-2][j-1]
                take = dp[i - 2][j - 1] + arr[i - 2]
                dp[i][j] = max(not_take, take)
        return dp[n + 1][picks]

    # Case 1: Exclude the last slice
    case1 = max_slices(slices[:-1])
    # Case 2: Exclude the first slice
    case2 = max_slices(slices[1:])
    return max(case1, case2)

# Example usage:
print(maxSizeSlices([1,2,3,4,5,6]))  # Expected output: 10
← Back to All Questions