There is an algorithm that, given a cutting of the pizza with n slices, performs a precomputation in time O(n). Then, during the game, the algorithm decides each of Alice’s turns in time O(1) in such a way that Alice makes at most two jumps and her gain is at least g(n)|P|.
Claim :
There is an algorithm that, given a cutting of the pizza with n slices, computes an optimal strategy for each of the two players in time O(n^2). The algorithm stores an optimal turn of the player on turn for all the n^2−n+2 possible positions of the game.
Open problem
Is there an algorithm that uses o(n^2) time for some precomputations and then computes each optimal turn in constant time?
See details
No comments:
Post a Comment