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.
I've just found it here: Shumen 2016.
I took a glance at the author's code and now my eyes hurt af. It'd be great if someone from Bulgaria could translate the solution.
A lot of cases (BTW two important conditions in the original problem not stated above, all Ai are different and greater than 0):
case 1: (N == K) X wins obviously
case 2: [K < N](K == 1) X wins iff there is a number in the input equal to the sum modulo P
case 3: [K < N, K > 1](K is even) Y wins as in its last move it has N — K + 1 different options (different modulo P as all Ai < P) to choose from, and at least one of them must make the sum distinct from 0 modulo P.
case 4: [K < N, K > 1, K is odd](N is even) Suppose we get to the moment when N — K + 2 numbers remain, so we have two moves left, one of Y and then one of X. Y must choose a number Ai such that the current sum minus Ai is not equal to any other remaining Aj, and in that case he/she wins. Suppose it's impossible for Y, so for each Ai there is an Aj (unique) such that (j ≠ i)Aj = sum - Ai. Observe this relation is symetric. But that's impossible, as all Ai must be different, and we have an odd number of different numbers modulo P left. So Y wins.
case 5: [K < N, K > 1, K is odd, N is odd](numbers Ai can be paired such that in each pair the sum is P, leaving only one number without pair) X wins by taking first the number without pair, and then after each move of Y, taking the other element in the corresponding pair.
case 6: [K < N, K > 1, K is odd, N is odd](The numbers Ai cannot be paired) Suppose we get to the moment when N — K + 2 numbers remain, so we have two moves left, one of Y and then one of X. Y can make sure easily that at this point at least two numbers cannot be paired with another such that the sum is P (in each move Y could take a number currently belonging to one such pair). Let's assume Y cannot win. This means that the numbers left, with sum S, in total N — K + 2, even, can be paired such that in each pair the sum is S. That means that S = S * (N — K + 2 ) / 2 mod P, that is, S = 0 mod P. But as we know, Y made sure at least two numbers could not be paired, so it's impossible to get to the losing state for him/her, so Y wins.
Overall many cases, not very interesting to play at home :)