GHVSSI - EDITORIAL

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. :slight_smile:

2 Likes

A slight mistake in the example given in the editorial, the next state should be (0,0,0,1,1) instead of (0,0,0,1,0) as stated above. :slight_smile:

1 Like

A few points here:

  1. Fairly obviously, for a given starting setup, the current state of Z is entirely dependent on the use of numbers to that point and so does not need to be part of the recorded state. Also, we never need to record anything about a value of Z that is 2\bmod 4 since this is an already-lost position.
  2. I’m reasonably convinced that the values 2 \bmod 4 only need to be recorded for parity also (like the 0 \bmod 4 set). The concept here is that if one player thinks using a 2 \bmod 4 number is a positive move, the other player can revert them to the previous state by playing another such. This would make the problem O(N^2).
  3. I solved this under Grundy numbers, and these showed more complexity than a simple win/lose - there were Grundy values up to 3. Nevertheless the values on smallish gridssupported my opinion in point (2) above, .
2 Likes

If your point 2 is correct, I believe that would also imply that a value of 1 \bmod 4 can be negated by a 3 \bmod 4, which brings complexity down to \mathcal{O}(N).

@meooow I don’t think that is (wholly) correct, since there are other options to play in those cases, although I think there is some more advantage to be had there.

Even I am not sure if second point is correct or not. Nice analysis though.