KFORK - Editorial

editorial
, , ,
1

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

5 Likes
2

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<n and j<n): break
            m[i][col] = False if m[i][col]!="Q" else "Q" # vertical
            m[row][i] = False if m[row][i]!="Q" else "Q" # horz
            # print "-"*10
        
        i, j = row, col
        while True:
            if not (i>=0 and i<n and j>=0 and j<n): break
            m[i][j] = False if m[i][j]!="Q" else "Q"
            i -= 1
            j += 1
        
        i, j = row, col
        while True:
            if not (i>=0 and i<n and j>=0 and j<n): break
            m[i][j] = False if m[i][j]!="Q" else "Q"
            i += 1
            j -= 1

        i, j = row, col
        while True:
            if not (i>=0 and i<n and j>=0 and j<n): break
            m[i][j] = False if m[i][j]!="Q" else "Q"
            i += 1
            j -= 1

        i, j = row, col
        while True:
            if not (i>=0 and i<n and j>=0 and j<n): break
            m[i][j] = False if m[i][j]!="Q" else "Q"
            i -= 1
            j -= 1

        i, j = row, col
        while True:
            if not (i>=0 and i<n and j>=0 and j<n): break
            m[i][j] = False if m[i][j]!="Q" else "Q"
            i += 1
            j += 1

        m[row][col] = "Q"
    res = 0
    # pprint(m)
    i = 0
    while(i<n):
        j = 0
        while j<n:
            # print m[i][j]
            if m[i][j]==True:
                posd = [(i+1,j+2), (i+1,j-2), (i-1,j+2), (i-1,j-2), (i+2,j+1), (i+2,j-1), (i-2,j+1), (i-2,j-1) ]
                qs = 0
                for p in posd:
                    row, col = p
                    if row>=0 and row<n and col>=0 and col<n:
                        # print row, col, "is possible"
                        if m[row][col]=="Q":
                            qs += 1
                            # print row, col, "is actually possible"
                if qs>=2:
                    res += 1
            j += 1
        i += 1
    print res
3

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).

4

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?

5

i did not understand the approach for diagonals. Please elaborate.