Pizza With 3n Slices

In this blog, you will solve the problem of Pizza With 3n Slices.

Problem Statement

 

Given a pizza with 3n slices of varying size, you and your friends will take slices of pizza as follows:

• You will pick any pizza slice.
• Your friend Alice will pick the next slice in the counter clockwise direction of your pick.
  
• Your friend Bob will pick the next slice in a clockwise direction of your pick.
  
• Repeat until there are no more slices of pizza.
  

The sizes of each pizza slice is represented by circular array slices in clockwise direction. And the problem is to find the maximum possible sum of slice sizes that you can have. Lets have an example to illustrate the problem, you are give the slice array as [ 1, 2, 3, 4, 5, 6 ] then the output will be 10. Firstly, you pick pizza slice of size 4, Alice and Bob will pick slices with size 3 and 5 respectively and then, pick slices with size 6, finally Alice and Bob will pick slice of size 2 and 1 respectively. So that makes the total to 10 (1st case: 4 + 2nd case: 6).

 

 

 

Given are some more examples and here is the leetcode problem,

static void Main(string[] args)
{
    var result = MaxSizeSlices(new int[] { 1, 2, 3, 4, 5, 6 });
    // example 1 : result = 10
    result = MaxSizeSlices(new int[] { 8, 9, 8, 6, 1, 1 });
    // example 2 : result = 16
    result = MaxSizeSlices(new int[] { 4, 1, 2, 5, 8, 3, 1, 9, 7 });
    // example 3 : result = 21
    result = MaxSizeSlices(new int[] { 3, 1, 2 });
    // example 4 : result = 3
}

Solution

 

To solve this problem we will use dynamic programming, which basically is dividing the main problem into sub problems, so that their results can be re-used and finally combined to get the solution for the main problem. Here, we will create all the cases that Alice, Bob and the person can have the slices, and store every case in a 2D array. And finally find the maximum size of the slice for the person. Here is the C# code for the approach,

public static int MaxSizeSlices(int[] slices)
{
    int n = slices.Length;
    int[] referrer = new int[2 * n];
    Array.Copy(slices, referrer, n);

    for (int i = 0; i < n; i++)
        referrer[i + n] = slices[i];

    int[,] cases = new int[2 * n, 2 * n];
    for (int i = 3; i <= n; i += 3)
    {
        for (int j = 0; j + i - 1 < 2 * n; j++)
        {
            int k = j + i - 1;
            for (int l = j + 3; l <= k - 2; l += 3)
                cases[j, k] = Math.Max(cases[j, k], cases[j, l - 1] + cases[l, k]);

            for (int l = j + 1; l < k; l += 3)
            {
                int clock = j + 1 <= l - 1 ? cases[j + 1, l - 1] : 0;
                int anticlock = l + 1 <= k - 1 ? cases[l + 1, k - 1] : 0;
                cases[j, k] = Math.Max(cases[j, k], referrer[l] + clock + anticlock);
            }
        }
    }

    int mySlices = 0;
    for (int i = 0; i < n; i++)
        mySlices = Math.Max(mySlices, cases[i, i + n - 1]);

    return mySlices;
}