PROBLEM LINK:Setter: Misha Chorniy DIFFICULTY:Easy PREREQUISITES:Counting, Implementation. PROBLEM:Given a field of $N*M$ dimension with King Chef being located at position $(X, Y)$, count the number of ways of choosing positions of two queens on the same field, such that they cannot see each other. If they see each other, it will be chaos (difficult choice for Chef :P) Chef's Queens, just like chess queens, can see in horizontal, vertical and diagonal direction, but cannot see through King Chef. SUPER QUICK EXPLANATION
EXPLANATIONThis problem actually has that much only to explain, as I did in super quick explanation, so, I'm sharing my idea, followed by another idea. First of all, we know, that both queens can see each other if they share a same row or column or diagonal and Chef isn't between two queens. Suppose, we fix position $(R, C)$ for the first queen. So, this queen can see in all elements of row R unless barred by Chef, which can happen if CHef and First Queen is in the same row, which happens when $R==X$. Similar explanation follows for the Same column and Same diagonal. Basically, this is all needed to implement the solution. For every position, we can see, that two positions are immediately unavailable, the positions of chef and queen. After that, we can count the number of positions in same diagonals (See that a position is lying in two diagonals, from top left to bottom right and the other one from top right to bottom left), as well as same column and diagonals. My Approach I Decided to count the unordered pairs of positions of both queens because it reduces number of cases to be considered. (We only need to consider two diagonals, only the part lying to the right of fixed position.) For a position $(R,C)$ i try to place other queen only in any column right to $(R, C)$, that is, a position with column greater than $C$. We see, that there are $(C1)*N$ such positions. But this includes various banned positions.
But, out of these positions, some of the positions may not be banned, due to chef being present in between. We can see, that these positions are
In the problem, pairs are ordered, that is, First queen may also lie to right of second queen. So, we multiply this count by 2. Hence, we have counted the number of ways to place queens without chaos in different columns. But we still need to count the number of ways to place queens in same rows as Chef. But these pairs are unordered. See, there are $(X1)$ empty cells above Chef's position and $(NX)$ empty positions below Chef's position in the same column. We can place the First queen in $(X1)$ ways and Second queen in $(NX)$ ways. We can also choose in two ways, whether to place the first queen in the upper position, or second queen. Hence, the total number of ways to place queens in the same row, with the chef in between, is $(X1)*(NX)*2$. Adding this to count above, we have found the number of ways to place queens on board without collision. Alternative solution There also exist faster solutions where we first count the total number of ways to place queens and then exclude position pairs, which lead to chaos. Small hint: For the same row, with the chef in between, there are $(Y1)*(Y2)/2+(MY)*(MY1)/2$ such position pairs. Can you find the whole solution? Can you generalize this form to diagonals? Share your solution in case you achieved this complexity during or after the contest. PS: Any Comments about Chef having two Queens waiting for him, Even causing chaos, just at sight of another queen? Lucky Chef xD. Time ComplexityTime complexity is $O(N*M)$ per test case for my solution, though it may also be possible to achieve linear or constant time complexity (I expect). AUTHOR'S AND TESTER'S SOLUTIONS:Setter's solution Feel free to Share your approach, If it differs. Suggestions are always welcomed. :)
This question is marked "community wiki".
asked 03 Nov '18, 17:30

Hello, @thucnguyen.when i just convert your code into python 2 (by simply replacing input() with raw_input() ) and submit the solution in pypy 2.6.0 and i get the correct answer(https://www.codechef.com/viewsolution/21485615 ). You can read an excellent explanation for this by @gorre_morre here answered 05 Nov '18, 22:59
Explanation link not working, fixed solution link.
(06 Nov '18, 16:11)
1
Everything fixed
(06 Nov '18, 17:06)

I had also been waiting for you Chef Taran ;) . To read this editorial! :) Thank you for taking my feedback and offering a detailed explanation. I seriously love your editorials! Looking forward to editorials of rest of the questions and November long :) answered 05 Nov '18, 01:59

I submited solution with the algorithm similar to the editorial above, in Python 3 and got Time Out. I then successfully implemented better approach (similar to alternative approach above) with time complexity of Full code is here: https://repl.it/@ThucNguyen1/CHQUEENS answered 05 Nov '18, 07:28
