Consider a doubly-ended queue with 1000 elements. Alice and Bob take turns to remove an element from either end of the queue. The player who removes a larger sum wins.
Who wins the game?
This problem appeared in IOI 1996 in Hungary, but it's a well-known puzzle by now.
![[home]](http://people.csail.mit.edu/mip/images/home.gif){kind=small}
13 comments:
Second player can't win.
We can assume that the elements are revealed at the beginning, right? :-) If that's the case then the first player can determine in O(n^2) the winning strategy. He can do this by finding in linear time what is the best strategy to leave each element as the last one be picked.
This problem is more fun when posed as a pizza: A pizza has an even number (1000?) of slices, of varying size. Players take turns taking slices: the first player can take any slice, but subsequent moves must take from the open end of the pizza. So its exactly the same as your problem, except the first player gets to choose where to define the ends of the queue. The goal is to take the most pizza. Since it is an even number of slices, we can two-color them. Either the red slices or the blue slices constitute a majority of the pizza, and the first player can guarantee he takes all slices of one color, thereby winning.
This problem becomes much harder when there are an -odd- number of slices: the two coloring trick no longer works. But of course as a two player game of perfect information, it must be that either the first player or the second player always can guarantee at least a draw. Who is it? What is the winning strategy?
under some assumption first player always wins. P1 takes sum of all odd indexed elements and even indexed elements and forces P2 to always choose element with index odd or even depending on which sum is smallest.
If sum of numbers with odd index is equal to sum of numbers with even index then some times P1 can force a win and some times P2 can force a draw. This can be found by a dynamic programming algorithm which runs in O(n^2) time.
I thought if we can get an algorithm which runs in O(n) time and finds the solution even when the sums are equal. Any ideas?
A similar problem: Two players have a chocolate with MxN squares. A move consists of (1) breaking the chocolate along a horizontal or along a vertical and (2) eating one of the two pieces. If only one square remains then it must be eaten. The bottom-right corner is poisoned. Who dies?
I spoke too early. The O(n^2) I described doesn't work but another one does: consider M(i,j) the maximum advantage that a player can obtain when playing first on a queue composed of V[i],...V[j]. M(i,j) = max(V[i]-M(i+1,j), V[j]-M(i,j-1)). We start with M(i,i) = V[i] and we fill the diagonals until we compute M(1,n).
But (as Anonymous indicated) this is only needed when the sum of numbers with odd index is equal to sum of numbers with even index.
About the chocolate problem: the player that eats the poisoned corner dies. :P A player can stay alive if he can leave the chocolate in a squarish shape after his move. This doesn't hold if the poisoned square is not in a corner. ;-)
Say the odd and even sums are equal. Determining the outcome (draw vs 1st player wins) in o(n^2) time seems interesting. I don't see how to do it yet.
In the same spirit, can we determine the optimal value for the first player in o(n^2)?
If we can determine optimal values, it's straightforward to extend the algorithm to determine optimal moves.
Then we can just play out the optimal "game" and see what the outcome has to be. If it's a draw, then P1, under best play, will draw or win. If it's a lose, then P1, under best play, could either lose, draw, or win. If it's a win, then P1 will have to win.
Many people have already remarked we can determine optimal values in O(n^2) time, so determining the outcome will be on the same order.
Charles: Yes, of course.
o(n^2) means "better than n^2".
Say if it were the case that O(n) algorithm does not exist. How do you go about proving such a result. Any ideas?
Mihai: Ah! Sorry about the misread.
Here is a simple heuristic. It does not seem very useful, but anyway. It gives a lower bound on the advantage the first player can get. V[1..2n] is the current state of the list. B(V) is the best advantage doable by first player starting the game on V. A(V) is the absolute value of the sum of odd elements minus sum of even elements. V[i..j] is the sublist from index i to index j.
Now, compute L(V) = max{min(A(V[2..2n-1])+V[1]-V[2n] , A(V[3..2n])+V[1]-V[2]) , min(A(V[2..2n-1])+V[2n]-V[1] , A(V[1..2n-2])+V[2n]-V[2n-1]) }
Then B(V) >= L(V), i.e., the sum of the current advantage, and L(V) gives you a lower of the final advantage for the first player, who can choose to remove the element that raises the lower bound the most. Maybe the only interest of the heuristic is that it takes linear preprocessing time and constant time per round (in a round, the two players play).
Since it is fast, the heuristic can be extended to explore 2^d level of the game-tree at each round. Can it be useful for solving the problem in o(n^2) time? Can we compute an upper bound in the same fashion?
Typo: replace "2^d levels" (at the end) by "a few levels"...
Post a Comment