PROBLEM LINK:Setter Oleksandr Kulkov DIFFICULTY:EASY PREREQUISITES:Observations, Strings, 2D arrays, Game Theory. PROBLEM:Given $2$ strings which tell if a player bringing coin to that cell wins or loses, we need to tell $Q$ queries asking "Who wins the game if game starts at $(x,y)$ and alice goes first?" QUICKEXPLANATION:Key to AC Observing winning and losing positions diagonally!! We have data to tell who wins if stone comes at $(0,i)$ or $(i,0)$. Use that to derive data of first $2$ rows. Use the observation that, winning positions dont change diagonally after row 2. (There are corner cases where they can change from row 1 to row 2 going diagonally, but they are guaranteed to remain constant thereafter). Now, store the states (whether player starting at that cell wins or loses) for first $2$ rows and first $2$ columns. After this, all thats left is to do this to make cases. If $(x,y)$ does not lie in first $2$ rows or first $2$ columns, find the corresponding cell in row/column $2$ diagonal to $(x,y)$ (if cell is not in row 1 or row 2 or column 1 or column 2) to find the answer, as states remain constant diagonally. If cell is in first $2$ rows or columns whose state we calculated above, we simply refer to it to answer the query. EXPLANATION:This editorial will have $2$ sections. We will be referring to first the brute force, and then deal with what we observed and how we used it to get full solution. First Subtask There was a lot of confusion in this question related to what does $0$ represent and what does $1$ represent, mostly because the question followed a different convention. Hence, to avoid any such confusion, let me denote $W$ as winning position, i.e. player starting from this cell wins, and $L$ by losing position, i.e. player starting from this cell loses. Lets first get how the games are played by the players. The only thing you need to remember is, for impartial games, usually the starting position itself determines the winner if players play optimally. If "playing optimally" is something that confused you in this question, read the paragraphs below in tab What does above mean (especially if you read the paragraphs in hidden tabs)? The starting position will determine the winner, and if we know states of previous cells then we can find states ($W$ or $L$) of current cell. All thats left is, finding a base case to start with so we can start finding if the position is $W$ or $L$. How do we do that....HMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM. The setter gave us $2$ strings, can we use them for this? Turns out we can :D I will denote the string also by $WLWLWWWL...$ to avoid any confusion regarding $0$ and $1's$. $W$ means player bringing stone at that position wins, and $L$ means he loses. We can move vertically up, or horizontally left. Hence, the states ($W$ or $L$) of only these 2 cells matter. For cell $(1,1)$ , we know the states of $(0,1)$ and $(1,0)$ in input. Once we get $(1,1)$, then along the row we can derive state of $(1,2)$ , and hence $(1,3)$ and hence $(1,4)$...and so on. Doing this for every row gives us states of all the cells. Now for every query, we see the state of given cell and accordingly append to the string. You know the base case, and also the recurrence (when and how to assign a state $W$ or $L$). Can you come up with a pseudo code to assign current state $W$ or $L$? Please let me make it clear. $W/L$ in matrix means player who starts his turn at that cell wins/loses, while $W/L$ in string means player who brings stone at that cell wins/loses. Answer is in tab below Full Solution Surprisingly, this section wont be long at all! The only difference between brute force and full solution is that, full solution observes (or proves) that diagonal elements after row 2 remain constant. Hence, while brute force tries to find the entire matrix, full solution derives the state of cell $(x,y)$ using cells in first $23$ rows and columns. (We only need cell which is lying "Diagonally backward" from $(x,y)$ in these rows.) Images and all those are fine, but how can one actually get the intuition? The most basic and commonly used method, of course, is observation. But proofs are needed to be done, so that we can verify and also better ourselves at such questions. I will first state the lemma's or rules, and then move on to prove them one by one. Proofs are in tabs, so that you can first attempt to derive them.
Proof of Lemma 1 Answer for 2. Proof for 3. Now, with this idea clear, how do we implement it? One of the neat implementations used by @um_nik ought to be discussed here :D.
Code for reference is in tab below SOLUTIONAuthor's solution can be found here. Tester's solution can be found here. Editorialist's solution can be found here. $Time$ $Complexity=O(N)$ CHEF VIJJU'S CORNER :D1. Is your idea same as editorial? Still got TLE? Make sure you done use $s=s+'1'$ for making the output string, as this method creates a completely new string and then adds '1' to end, making it $O(N^2)$! Use $s+=1;$ for better performance. Just like creating a new vector to add an element at last v/s adding an element at back of vector. 2. At the end of the day, I'd want you to remember the part of $W$ and $L$ which we discussed. You can apply that to any such game. If starting position determines winner, and you know the state of positions which you can visit from current cell, you can derive for this cell as well. A player wins only if he can force his opponent to lose by making sure opponent plays only at "losing" or $L$ cells. Hopefully this will clear the numerous doubts among div2 guys on what "playing optimally" is :) 3. Often I am asked, what does a coder truly do to ace all the contest's problems? 4. Setter's Notes (his solution isnt based on observations) 5. Related Problems: asked 13 Sep '18, 01:13

I was able to get AC using brute force approach implemented with bitwise operations. Let's say U1 is the bitwise representation of a diagonal (coming from top right to bottom left), then the next diagonal U2 can be calculated as: U2 = ~(U1 & (U1<<1)). Plus the bits corresponding to the boundary conditions need to be overriden when necessary. Using bitset would still cause TLE, so need to manually implement bitset functionality using array of unsigned long long's and apply operations only to the necessary elements. answered 20 Sep '18, 19:29

can you please explain why l at 1,3. answered 17 Sep '18, 20:20

I have a doubt ....its a mistake but I want to ask why my approach is wrong? my solution
thanks in advance... answered 18 Sep '18, 22:23

if someone still needs soln(commented) he can refer mine i had mapped all the diagonal element answered 18 Sep '18, 23:41

I successfully solved this question during the live contest but implementation of my code was getting wrong everytime. Hard luck! answered 20 Sep '18, 00:59

I read this editorial twice but still can't get the intuition behind making two separate cases for filling row1,col1 and row2..n,col2..n. Can someone make me understand this part ?
Thanks in advance :) answered 18 Oct '18, 11:25
Which line made you think that you HAVE to fill ONLY that way? I might help there! You can fill anyway if I recall correctly there are multiple valid ways out of which any can be chosen.
(18 Oct '18, 11:37)
actually, I am not able to understand this part. Could please provide comments over filling of the table for row 1. Row 1
Here, if A[0][j]=='W' then why A[i][j]='W'??
(18 Oct '18, 12:06)
1
Assume 1 based indexing, where $A[0][j]$ represents the j'th character in string (just like shown in pciture, string character above column). If ending up on that cell is $W$, then I will just move my cell to that and win. Dont assume Row 1 corresponds to 0'th index in array. 0'th index is for string.
(18 Oct '18, 12:57)
@vijju123 could you provide your solution for this problem as above links are not working.
(18 Oct '18, 14:40)
I have to ask @admin to fix link to setter's codee :/ . There was no code of setter at testing page else Iwould have pasted it. It was with @admin . There wasnt any editorialist solution, idk which solution he linked lol. You can refer to @um_nik 's code for now  its based on editorial except that it calculates for first 10 rows. I will try to upload my solution by evening.
(18 Oct '18, 15:15)

My solution answered 04 Nov '18, 20:15

Can I somehow get test data for past problems, that my solution failed? It is often very helpful for debugging. For any problem, not for this one.