Problem Link:Difficulty:MediumHard Prerequisites:2player Impartial games, linesweep Explanation:Some definitions: Characterization of losing and winning cells: Firstly, if there were no bad cells, then the set of losing cells would look like:
We now sweep a horizontal line, and keep track of "winning columns". These "winning columns" are those set of cells in the current row, from which there exists a columnmove that is winning. Note that these "winning columns" correspond to earlier losing cells, so we should also be interested in which all cells of the current selected row are "losing" (since they will give us our "winning columns" in future rows). Each contiguous set of cells that aren't bad would have atmost one losing cell. In fact, the losing cell (if it exists) would be the leftmost column that is "not winning". A good way to store these "winning columns" would be in the form of segments [L R]. Now, adding a new column to this only amounts to increasing a winning segment by 1, and possibly merging two earlier disjoint winning segments. However, sweeping our line row by row is potentially very slow. Instead, we sweep our line only over rows having bad cells. We divide our rows thus into two types:
Good blocks are sets of consecutive rows having no bad cells. We need to handle this separately since these would require us to modify our "winning segments" appropriately before encountering further bad rows. Also, in order to lookup segments quickly, we will store them in a balanced BST (such as STL set) S. Initially, the winning segments set S is empty. Now, Case 1. We encounter bad row x. Suppose the winning segments and the row x ("B" denotes bad cell) looking like:
This can be done by:
This handles maintaining of "winning segments of columns". We would still like to find losing cells of this row. The logic behind finding such losing cells has been described above (since this is just a singlerow shift). Introduce for simplicity two dummy bad cells (x, 1) and (x, inf). Now, in every contiguous set of nonbad cells, the leftmost nonwinning column would correspond to a losing cell.
The process of adding [y,y] to S should ensure that you should also merge segments as required
Thus we can handle bad rows in time O(logN) operations. Case 2. Handling a good block. Also remember that we have a current "winning segment set S" that has information at bad row x1, and we need to modify this information before it reaches bad row x2, as well as add any losing segments. Taking an example:
What this means is, we need to add diagonal segments whose total length is x2x11 for which their yranges do not intersect with each other or with the previous winning segments from S. Finally, some of the initial segments will be deleted while forming one large consecutive winning segment in the beginning. Pseudocode for this updating is as follows
Although it may seem that we may add many diagonal segments (like O(N^2)), but consider the following amortized analysis. Consider there to be X good block (X <= N), and Y is the number of segments that are added to S. It can be seen that Y = O(N). Then, the total number of losing diagonal segments we add will be at most 2*X + Y. Hence we get O(N log N) algorithm for finding the losing cells. The only thing left is to answer the queries. But this is simple. Since losing segments are diagonal, if we were to sort them by (xy), (and then by x to break ties), we just search of "segment" (x, y, 1) among these diagonal losing cells. If (x, y) belongs to the found segment, then it is a losing cell, else it cannot belong to any other losing segment and hence it is a winning cell. Overall, this algorithm is O(N log N + Q log N). Author's Solution:Can be found here Tester's Solution:Can be found here
This question is marked "community wiki".
asked 24 Dec '12, 04:50

please help....this is my first question here...i failed bcuz of time optmization can someone help include <stdio.h>main() { int i,j,k,c=1,f=1,p,z,T,N,Q; scanf("%d",&T);
} answered 03 Dec '14, 21:58

I was trying out to solve this and thought it recursively. I am facing some implementation problems in my code so I can't check if my logic is correct or not. Can you help me in telling if i am right or not.
Logic : I input a this position from where the alice will start the game. From here I will keep calling the same routine again and again recursively to check who wins at each of the block if the other player had started the game. It gives the answer finally. Following is my code link. Any help or views regarding this would be appreciated and I will be thankful to you.
http://ideone.com/F3QfLn
:D :D
The implementation is by and large correct, I can't find any bugs in it. However, this kind of algorithm is way too slow. This kind of recursion without even memoizing will have exponential time complexity O(2^(x+y)) for each query point (x, y). It will time out for grid sizes even 25x25.
hmm.....okay ya i agree upon its inefficiency.