PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Setter: Jafar Badour
Tester: Hussain
Editorialist: Taranpreet Singh
DIFFICULTY:
Easy-medium
PREREQUISITES:
Number-theory, Game Theory Minimax Algorithms and Dynamic Programming.
PROBLEM:
Given N numbers in array A and a Sum initialized to 0, Player in each turn, choose a number from A, erase it from A and add it to Sum. If Sum cannot be represented as a^2-b^2 for some positive integers a and b, the player last to move loses. If there is no number left in A, the player last to move wins.
QUICK EXPLANATION
-
Understand that the all the numbers which cannot be represented as $a^2-b^2$ are actually the numbers of form $4k+2$ for some integer k. -
For every number $A[i]$, only it's remainder modulo 4 matters. -
So, we reduce actual problem to - Given an array of numbers with $0 \leq A[i] < 4$, choose number where Numbers of form $4k+2$ are losing states.
EXPLANATION
First of all, let us understand what this weird constraint Z=a^2-b^2 means. For sake of convenience assume a>b. Writing a^2-b^2 as (a+b)(a-b). let x = a-b, then Z = x(x+2*b).
If x is odd, then x+2*b is also odd and vice versa. Hence, we know that both a+b and a-b have same parity.
If both a+b and a-b are odd, Z is odd, hence, all odd values can be written in above-mentioned form.
If both a+b and a-b are even, Z = 4*k for k = ((a+b)/2)*((a-b)/2).
Analyzing every number \bmod 4, we can reach every value of form 4*k, 4*k+1 and 4*k+3. Hence only numbers which cannot be reached are numbers of form 4*k+2.
Now, only the residue modulo 4 matters, so we can just take A[i] \bmod 4 and count numbers of values leaving residue 0, 1, 2 and 3.
Now, Moving toward Game theory, i would recommend reading this and this first. See the secret box for a start!!
Click to view
Every game has some unique parameters which uniquely define the outcome assuming optimal moves from both sides. THis means, a player makes a move which lead him to win as soon as possible, or delay loss as much as possible.
We label each state as winning if the player first to play from this position can win assuming optimal moves from both sides.
A state is losing if all the states it leads to in exactly one move are all winning states. Otherwise it is a winning state.
Above is the crux of Game theory Minimax Algorithms and just think about this whenever you want to solve a game theory problem.
Now, we can even simulate the whole process, that is, check every possible sequence of numbers, but this approach have exponential complexity which will time out, so, we have to resort to our best friend in hard times - Dynamic Programming.
Let us consider numbers left modulo 4 and current sum as combinations (r0, r1, r2, r3, cur), where r_i is number of elements \bmod 4 and cur means current sum \bmod 4.
Consider combination (0,1,0,1,0). Suppose current player use A number with residue 1, other player will try to win from combination (0,0,0,1,1) which in turn calls (0,0,0,0,0). This way, we can see that there can be a number of similar sub-problems, whose results will be used multiple times, pointing toward Dynamic Programming. For every combination, we store its result once computed, and the lookup from Table. This way, we need to fill Table of dimension r0*r1*r2*r3*4 with constraint r.+r1+r2+r3 = N. This is too much to store, Cannot we reduce it??. Turns out we can.
We can see that more than one occurrence of values with residue 0 is useless, since it doesn’t affect cur \bmod 4 at all. So, We can just take 0 \bmod 2 before computing. reducing complexity by a factor of N.
A bit more about DP Transitions in case you still didn’t get it, see the secret box.
Click to view
We have a combination (a,b,c,d,cur). If we choose a number with residue 1, we check if cur +1 \bmod 4 \neq 2 and see if (a,b-1,c,d,(cur+1) % 4) is a losing state or not. We do the same for every residue and if any leads to a losing state, current state is a winning state.
Time Complexity
In this problem, complexity depend upon actual values of A. We fill the whole result table of dimension 8*r1*r2*r3 in worst case, So, complexity would depend upon r1, r2 and r3. Assuming Even distribution, The time complexity would be of order O(N^3) per test case but the number of positions which are never reached is too high, So, To say, actual performance is much better than O(N^3). Anyone who can provide a stricter upper bound on time complexity is most welcomed.
Another thing, Usually we fill whole table and answer queries in O(1), but in problems where many states are unreachable, it may be better to fill only required values.
AUTHOR’S AND TESTER’S SOLUTIONS:
Setter’s solution
Tester’s solution
Editorialist’s solution
Feel free to Share your approach, If it differs. Suggestions are always welcomed. 
