Difficulty : Simple
Pre-requisites : 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.
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 N2 queens, we will have the complexity of O(N3). 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 i-th 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 X-Y. This way we can mark all the cells that are under attack of a single queen in O(M) time, i.e. in O(N2).
After this is done, we can just check every single cell. There are O(N2) 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(N2)