Pie Slices With Two Friends
Problem
A round pie is cut into 3n slices of different sizes, arranged in a circle. You take any remaining slice, then one friend takes the remaining slice just before it on the circle and another friend takes the remaining slice just after it. This repeats until the pie is gone. Return the largest total size you can collect.
Examples
Input: slices = [4, 1, 2, 8, 3, 5]
Output: 13
Why: take 8 (friends take 2 and 3), then take 5 (friends take 4 and 1)Input: slices = [8, 1, 1, 1, 1, 8]
Output: 9
Why: the two 8s touch across the join of the circle, so taking
one always hands the other to a friendInput: slices = [5, 2, 7]
Output: 7
Why: edge case, one round: take the biggest sliceHints
0 / 3
Play a few rounds by hand and look at which sets of slices you can end up with. Can you ever collect two slices that were next to each other at the start?
You never can, and any n slices with no two next to each other can be collected if you take them in a good order. So the game is really: pick exactly n slices, no two adjacent on the circle, with the largest sum.
The first and last slices are neighbours, so solve two straight-line versions, one without the first slice and one without the last. On a line, the best total from the first i slices with j picks is the larger of skipping slice i and taking it plus the best from the first i - 2 slices with j - 1 picks.
Solution
Taking a slice always hands both of its current neighbours to your friends, so the slices you collect are never adjacent on the original circle. In the other direction, n slices with no two adjacent can always be collected: take a wanted slice that sits next to a run of at least two unwanted slices, and the rest stay separated. So the game is house robber on a circle with exactly n picks. Dropping the first slice or the last slice breaks the circle into a line, and the better of the two lines is the answer; the line table has a row per slice and a column per pick count, and only two rows are kept. Time is O(n²) and space is O(n).
def best_share(slices):
picks, NEG = len(slices) // 3, float("-inf")
def best_line(a):
# rows of best[i][j]: the most from the first i slices using exactly j picks
two_back, one_back = [0] + [NEG] * picks, [0] + [NEG] * picks
for x in a:
row = [0] + [max(one_back[j], two_back[j - 1] + x) for j in range(1, picks + 1)]
two_back, one_back = one_back, row
return one_back[picks]
# the first and last slices touch, so never allow both
return max(best_line(slices[1:]), best_line(slices[:-1]))
print(best_share([4, 1, 2, 8, 3, 5])) # -> 13
print(best_share([8, 1, 1, 1, 1, 8])) # -> 9
print(best_share([5, 2, 7])) # -> 7Stuck on the idea rather than the code? House Robber in a Circle covers it.