Problem link : contest practice Difficulty : Simple Prerequisites : Basic programming language concepts Problem : Find the number of ways to put a black knight on a chessboard with a number of white queens that it would make a fork. Explanation : It is not very hard to see that if we put a white queen to some cell of the chessboard, all the cells that are on the same vertical, horizontal or a diagonal will be blocked for putting a black knight there because that queen will have a possibility just to kill this black knight, so there will be no fork. If we mark all the cells that are under attack for every queen the solution will be far too slow, because there are O(N) such fields and if we have about N^{2} queens, we will have the complexity of O(N^{3}). In this problem N equals to 1000, so this solution is unapplicable here. Instead of marking every single cell we can mark the whole diagonal, horizontal and the diagonal. We can store, for example, boolean arrays AttackedRow[] and AttackedColumn[], where the ith element will be true if the correspondent row or column is attacked. Then, if we get the queen put at the cell (X, Y), then AttackedRow[X] and AttackedColumn[Y] will be true. Regarding diagonals, there are two kinds of them: those that go from the bottom left corner of the board and those that go from the top left corner of the board. So here we can make arrays AttackedDiagonal1[] and AttackedDiagonal2[] for these two kinds of diagonals. And if we have the white queen put at the cell (X, Y) the correspondent diagonal numbers will be X+Y and XY. This way we can mark all the cells that are under attack of a single queen in O(M) time, i.e. in O(N^{2}). After this is done, we can just check every single cell. There are O(N^{2}) cells and we can check that the cell is not under attack in O(1) time. Then we just count the number of cells with queens attacked by the knight from this position. There are only 8 possible candidates for every cell, so the solution complexity remains O(N^{2})
This question is marked "community wiki".
asked 27 Apr '14, 14:00

Hi, I tried this code, It works on my PC for big test cases(8 by 8 boards, i.e subtask 1) too, but it throws and nzec on the server, as seen here.
answered 30 Apr '14, 18:38
I've tried using xrange instead of while before. I thought it must be an overflow for xrange(it doesn't accept anything that doesn't fit in a C long I think).
(30 Apr '14, 18:39)

but what if we did the O(n^3) way, if its not giving a tle, why should it give a wrong answer for this? answered 01 May '14, 07:57

i did not understand the approach for diagonals. Please elaborate. answered 10 May '14, 12:40
