Can someone please explain the solution of problem from the last cook off GHVSSI.
Hi,
Here there are 4 choices for a,b i.e (even,even) , (even,odd) ,(odd,even) ,(odd,odd).Among the four choices first and last leave remainder of 0 when divided by 4 because (odd- odd) is even and (odd+odd) is even , similarly is the case for (even,even). But for (odd,even) let us say odd=2k+1 and even=2m ,Now (odd-even)(odd+even) =((4kk)+(4k)+1-(4mm)) which clearly gives u a remainder of 1 when divided by 4. Now even=2m and odd =(2k+1) then (even-odd)(even+odd)=(4((mm)-(kk)-k)-1) which clearly is 3 mod 4.
Hence for a number to be represented as (a^2-b^2) it should be of the form (4k) or (4k+1) or (4k+3) but not of the form (4k+2).
Here we r saying mod 4 because numbers are usually represented by 2k or 2k+1, so if we square we get numbers of the form 4*k+remainder.
Now the problem reduces to game theory as explained in the editorial .
Main point: 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.
So we check for all possible positions(in single move) from the given location, If any of these positions is a losing position then the current position is a winning position.
See the editorial for the code .Thanks
2 Likes
Actually what i did was checking if there is number x in the array such that adding this number with z makes the value of z of the form a^2 - b^2, and if such x exists than i would take this number and move on to next step. And if at any step i am not able to find the number x then i would break the loop and check who is the winner according to the number of steps taken.
I am not getting why this approach is not working, can you please tell.
my code : link
Also, you can search for editorials by tags. Mostly editorials have tag for contest code, problem code.
Also, try discuss.codechef.com/problems/PROB_CODE this would show editorial in most cases.
1 Like
actually i searched but didn’t found, but now i got the way to search thanks
No problem 
can someone please tell why this approach is wrong.
It’s hard to generate a test case right now, but the flaw in your approach is, that there might be multiple values, which may be valid at current step (doesn’t lead to reaching number of form 4k+2), but is a losing move as i explained in editorial.
If you still want a test case, make a random generator, compare outputs of your solution with that of and correct solution.