You are not logged in. Please login at www.codechef.com to post your questions!

×

KFORK - Editorial

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

xcwgf666's gravatar image

6★xcwgf666 ♦♦
719436377
accept rate: 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<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
link

answered 30 Apr '14, 18:38

svineet's gravatar image

3★svineet
362410
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★

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?

link

answered 01 May '14, 07:57

krishmakochhar's gravatar image

3★krishmakochhar
1
accept rate: 0%

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

link

answered 10 May '14, 12:40

fig12_yo's gravatar image

1★fig12_yo
1
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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