Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

Winkler's pizza picking problem:

  • A circular pizza pie of n slices, where slice i has area S_i i.e, the area is different for each pie piece.
  • Eaters Alice and Bob take turns picking slices, but it is rude to create multiple gaps in the pie (consider it not allowed).
    • Thus each eater is restricted to taking one of the two slices adjacent to the open region. Alice goes first, and both eaters seek as much pie as possible.

How would a dynamic programming algorithm determine how much pie Alice eats, if both Alice and Bob play perfectly to maximize their pizza consumption?

My understanding:

In a general DP problem, we go forward with finding sub-problems which can be visualized using recursion tree or, more tightly, using a DAG. Here, I'm not finding any lead to find the sub-problems here.

Here, for a given set of S_i s, we need to maximize the area of slices eaten by Alice. This will depend on choosing a permutation of Pizza slices out of (n-1) permutations. Choosing a max area slice out of two options available in every n\2 turns Alice gets, will give us the total area of slice for a permutation. We need to find area of slice for all such permutations. And then the maximum out of these.

Can somebody help me out on how to go forward?

share|improve this question

migrated from stackoverflow.com Dec 10 '11 at 19:33

This question came from our site for professional and enthusiast programmers.

add comment

2 Answers 2

Start by considering the slices just placed on a row and you can pick from one of the two ends. In this case supposing it's your turn to chose it's clear that pizzaAmount(slices) is

  1. If there's no pizza left result is 0
  2. If there's only one slice result is that slice
  3. If there are at least two slices then the result is:

(using Python syntax)

max(slices[0] + sum(slices[1:]) - pizzaAmount(slices[1:]),
    slices[-1] + sum(slices[:-1]) - pizzaAmount(slices[:-1]))

in other words you should consider both alternatives and that after taking your slice you will get all the remaining pizza except the result of the recursive call (because your friend will use the same strategy).

You can implement this with DP (or memoizing) because the array is indeed fixed and you can just consider as parameters the first and last slice index.

To solve the original full problem you just need to try all slices as starting slice and chose the one that maximizes the result.

share|improve this answer
    
Thanks "6502". I can visualise the problem better by utilising the hint of "considering the slices just placed on a row and picking from one of the two ends". Given recurrence relation is taking care of the optimal choice by the opponent, as well. I'll post a formal algorithm soon. Thanks guys!! –  ami Oct 31 '11 at 22:52
    
Just curious, what is the order of complexity for this algorithm? 0(n * 2^n)? –  Akron Oct 31 '11 at 23:28
    
@Akron: This is what it would be without a dynamic programming approach or memoization. However you can take advantage of the fact that the result of pizzaAmount does depends only on what are the start and stop index of the remaining slices and not on the sequence of which pizza slices you and your friend already ate so you can store the result in a matrix to avoid recomputation. The order of the algorithm is therefore O(n**2). –  6502 Nov 1 '11 at 6:22
    
If anyone is still struggling to understand, this link has a very nice explanation. –  ami Mar 3 '12 at 22:35
add comment

For part of pizza define F(i,j) as maximum how much person that first picks slice can eat. Slices of part of pizza (i,j) are:

if i <= j than slices i, i+1, ..., j-1, j
if i > j than slices i, i+1, ..., n-1, n, 1, 2, ..., j-1, j
and we don't define it for whole pizza, abs(i-j) < n-1

Define R(i,j) (how much left for second person) as sum(S_x, x in slices(i,j)) - F(i,j).

With:

F(i,i) = S_i,
F(i,j) = max( S_i + R(i+1,j), S_j + R(i,j-1) ),

maximum that Alice can eat is calculated by:

max( S_i + F(i+1, (i-1) if i > 1 else n) ).
share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.