POOK Editorial

editorial
, ,
1

PROBLEM LINK:

Contest Division 3
Contest Division 4

Setter and Editorialist : Yashodhan Agnihotri

DIFFICULTY:

1121

PREREQUISITES:

None.

PROBLEM:

Find the maximum number of pooks on an N x N chessboard such that none of them threaten each other. A Pook has the properties of both, a pawn and a rook.

EXPLANATION:

We will see 4 cases here. The three cases of N = 1,2,3 need to be handled separately while N \geq 4 will follow the answer of the N-Queen Problem. Since we can place atmost N unthreatening rooks on a N x N chessboard, therefore as a Pook has all the properties of Rooks, we would be able to place atmost N pooks as well.
The answer for the N-Queen problem for N greater than 4 is N queens, therefore our answer will also be the same here.

N = 1

Since there is just one square, we can place 1 pook in it.

N = 2

Here, we can place just 1 pook, since all the other three squares will be threatened by it.

N = 3

Here, however you place the pooks, you cannot place more than 2 pooks on the board.

N >= 4

Here, the answer is same as the N-Queen Problem i.e N pooks.

SOLUTIONS:

Setter's Solution 
#include<bits/stdc++.h>
using namespace std;

int main() {
	int t;
	cin >> t;
	while (t--) {
		int n;
		cin >> n;
		if (n == 2 || n == 3)
			cout << n - 1 << "\n";
		else
			cout << n << "\n";
	}
	return 0;
}

For doubts, please leave them in the comment section, I’ll address them.

2 Likes
2

on what position can we put pook, for n=4, i can figure out only 3 position.

1 Like
3

considering a 4*4 grid (0 based indexing) , these are the following index
(1,0) (3,1) (0,2) (2,3) .

2 Likes
4 
  n = 3       n = 4        n = 5           n = 6            n = 7             n = 8
    2           4            5               6                7                 8

  p * *      * p * *     p * * * *      * p * * * *      p * * * * * *      * p * * * * * *
  * * p      * * * p     * * p * *      * * * p * *      * * p * * * *      * * * p * * * *
  * * *      p * * *     * * * * p      * * * * * p      * * * * p * *      * * * * * p * *
             * * p *     * p * * *      p * * * * *      * * * * * * p      * * * * * * * p
                         * * * p *      * * p * * *      * p * * * * *      p * * * * * * *
                                        * * * * p *      * * * p * * *      * * p * * * * *
                                                         * * * * * p *      * * * * p * * *
                                                                            * * * * * * p *
8 Likes
5

got it