How to solve this game-theory problem?

Revision en1, by xuanquang1999, 2017-03-12 12:51:17

I have recently encounter this game-theory problem:

"Two player X and Y is going to play a game. Initially, they choose a number P (P ≤ 1018) and a set of number A1, A2, A3, ..., An (n ≤ 5000, 0 ≤ Ai < P). They will take their turns alternatively. In each turn, one player will remove a number from the set. After K turns, if the sum of all remaining numbers in the set is divisible by P, player X will win. Otherwise, player Y will win.

Determine who will win the game, if both of them play optimally. (The name of player who make the first move will be given in the input)"

I completely have no efficient approach for this problem (except the naive bitmask DP). Can anyone give me an hint? Thanks in advance.


  Rev. Lang. By When Δ Comment
en1 English xuanquang1999 2017-03-12 12:51:17 782 Initial revision (published)