PROBLEM LINK:
Setter: Misha Chorniy
Tester: Hasan Jaddouh
Editorialist: Taranpreet Singh
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
- Fix position of one queen, and try to count the number of positions where the other queen may reside, without causing chaos.
EXPLANATION
This 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 (C-1)*N such positions.
But this includes various banned positions.
- which are in the same row as the First queen. There are M-C such positions.
- sharing diagonal coming from upper right direction. We can prove that there are min(M-C, R-1) such positions. After these steps, we will either reach the top or right border after these many steps.
- sharing diagonal coming from bottom right direction. We can prove that there are min(M-C, N-R) such positions. After these steps, we will either reach the bottom or right border after these many steps.
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
- If sharing the same row as Chef, and Chef lies to the right of Queen, then there are (M-Y) such valid positions.
- If sharing same diagonal coming from upper right direction, there are min(M-Y, X-1) such valid positions.
- If sharing same diagonal coming from bottom right direction, there are min(M-Y, N-X) such positions.
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 (X-1) empty cells above Chef’s position and (N-X) empty positions below Chef’s position in the same column. We can place the First queen in (X-1) ways and Second queen in (N-X) 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 (X-1)*(N-X)*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 (Y-1)*(Y-2)/2+(M-Y)*(M-Y-1)/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 Complexity
Time 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
Tester’s solution
Editorialist’s solution
Feel free to Share your approach, If it differs. Suggestions are always welcomed. 
. To read this editorial! 