×

# KFORK - Editorial

 6 Problem link : contest practice 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. 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 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) Solutions: Setter Tester This question is marked "community wiki". asked 27 Apr '14, 14:00 719●43●63●77 accept rate: 0%

 0 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. Code: from __future__ import division def read_mapped(func=lambda x:x): return map(func, raw_input().split(" ")) def read_int(): return int(raw_input()) from pprint import pprint T = read_int() for case in xrange(T): n, mnum = read_mapped(int) m = [[True]*n for _ in xrange(n)] for _ in xrange(mnum): col, row = read_mapped(int) col = col - 1 row = row - 1 for i in xrange(n): # print "Going through:", i, col, " and ", row, i # pprint(m) # if not (i=0 and i=0 and j=0 and i=0 and j=0 and i=0 and j=0 and i=0 and j=0 and i=0 and j=0 and row=0 and col=2: res += 1 j += 1 i += 1 print res  answered 30 Apr '14, 18:38 3★svineet 36●2●4●10 accept rate: 0% 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) svineet3★
 0 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 1 accept rate: 0%
 0 i did not understand the approach for diagonals. Please elaborate. answered 10 May '14, 12:40 1★fig12_yo 1 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,851
×1,191
×20
×6

question asked: 27 Apr '14, 14:00

question was seen: 7,226 times

last updated: 10 May '14, 12:40