QUEENBL - Editorial

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: S. Manuj Nanthan
Testers: Nishank Suresh, Tejas Pandey
Editorialist: Nishank Suresh

DIFFICULTY:

1946

PREREQUISITES:

Observation

PROBLEM:

You are given the position of a king on an 8\times 8 chessboard. Place the minimum number of queens such that they don’t attack the king, but the king also cannot make a move.

EXPLANATION:

There are a couple of ways to solve this problem, though for the most part they all rely on the following observation:

  • It is always possible to create a valid configuration using \leq 2 queens

One way of approaching this problem is with casework. There are a handful of different cases that need to be covered, all needing one or two queens in different configurations:

  • Case 1: the king is in one of the four corners (needs one queen)
  • Case 2: the king is along the border of the board, but not in a corner (2 queens)
  • Case 3: the king is one square away from the border and close to a corner (2 queens)
  • Case 4: any position that is not in cases 1 and 2 (2 queens)

However, I will describe a simpler way to approach the problem, with far less thinking and casework required: simply bruteforce the positions of the queens!

It’s obvious that 4 queens will always suffice to achieve what we want - just use one to cut off each row/column around the king.

After trying out a couple of cases, you might notice that you can always do it with 2 queens. However, maybe you aren’t satisfied: perhaps there’s a case you missed that needs 3 queens.

So, for now let’s assume that we always need \leq 3 queens, and bruteforce all options. The number of ways of placing \leq 3 queens on the board is bounded by 64\times 64\times 64. There are only 64 possible inputs, and for each combination of (king position, queen positions) we need to check whether each queen attacks the king and the squares around it, leading to a total of somewhere around 64^4 \cdot 9 \cdot 3 operations.

At first glance, this is too many operations to perform within one second. However, the constant factor can be optimized in several ways:

  • Note that we cannot place a queen at a position that attacks the king. Once the king’s position is known, this removes every square from its row, column, and diagonals from consideration. This leaves us with somewhere between 30 and 40 valid positions, bringing down the constant to 64\cdot 40^3 instead (in practice, it’s a lot less since all the middle positions give us ~30 valid squares.
  • The above optimization is already enough to receive AC (in C++), however more optimizations can be made. For example, symmetry of the board allows us to solve for only the 8 cells of the form (i, j) where 1 \leq i \leq j \leq 4, and then suitably reflect/rotate the answer to obtain the solution for any other cell
  • Another option is to precompute all the answers offline, then store them in the code and simply print the answer when submitting. This essentially turns the time limit into 3 hours (the contest’s duration) instead of one second.

Of course, noting that the answer is \leq 2 also immediately makes even our first bruteforce fast enough since it cuts out a factor of 64.

CODE:

Setter's code (Python, casework)
#from itertools import *
#from math import *
#from bisect import *
#from collections import *
#from random import *               # ( : ): ( :) : (: ) : (  ): ) : )
#from decimal import *
#from heapq import *
#from itertools import *            # Things Change ....remember :)
import sys
input=sys.stdin.readline
def inp():
    return int(input())
def st():
    return input().rstrip('\n')
def lis():
    return list(map(int,input().split()))
def ma():
    return map(int,input().split())
def valid(x,y):
    if(x<=0 or x>8 or y<=0 or y>8):
        return 0
    return 1
t=inp()
while(t):
    t-=1
    x,y=ma()
    res=[[0 for i in range(8)] for j in range(8)]
    res[x-1][y-1]=1
    if(x==1 and y==1):
        res[2][1]=2
    elif(x==1 and y==8):
        res[2][6] = 2
    elif(x==8 and y==1):
        res[5][1] = 2
    elif(x==8 and y==8):
        res[5][6] = 2
    elif(x in [1,8] or y in [1,8]):
        if(x==1):
            res[x+1][y-2]=2
            res[x+1][y]=2
        if(x==8):
            res[x-3][y-2]=2
            res[x-3][y]=2
        if(y==1):
            res[x-2][y+1]=2
            res[x][y+1]=2
        if(y==8):
            res[x-2][y-3]=2
            res[x][y-3]=2
    else:
        flag = 0
        for i1 in [-1,1]:
            for i2 in [-2,2]:
                for i3 in [-3,3]:
                    for i4 in [-1,1]:
                        x1,x2 = x+i1 , x+i3
                        y1,y2 = y+i2 , y+i4
                        if(valid(x1,y1) and valid(x2,y2) and flag==0 and ((i1>0 and i3<0) or (i1<0 and i3>0)) and ((i2>0 and i4<0) or (i2<0 and i4>0))):
                                res[x1-1][y1-1]=2
                                res[x2-1][y2-1]=2
                                flag=1
    for i in res:
        print(*i)
Tester's code (C++, brute force)
#include <bits/stdc++.h>
using namespace std;

long long readInt(long long l,long long r,char endd){
    long long x=0;
    int cnt=0;
    int fi=-1;
    bool is_neg=false;
    while(true){
        char g=getchar();
        if(g=='-'){
            assert(fi==-1);
            is_neg=true;
            continue;
        }
        if('0'<=g && g<='9'){
            x*=10;
            x+=g-'0';
            if(cnt==0){
                fi=g-'0';
            }
            cnt++;
            assert(fi!=0 || cnt==1);
            assert(fi!=0 || is_neg==false);

            assert(!(cnt>19 || ( cnt==19 && fi>1) ));
        } else if(g==endd){
            if(is_neg){
                x= -x;
            }

            if(!(l <= x && x <= r))
            {
                cerr << l << ' ' << r << ' ' << x << '\n';
                assert(1 == 0);
            }

            return x;
        } else {
            assert(false);
        }
    }
}
string readString(int l,int r,char endd){
    string ret="";
    int cnt=0;
    while(true){
        char g=getchar();
        assert(g!=-1);
        if(g==endd){
            break;
        }
        cnt++;
        ret+=g;
    }
    assert(l<=cnt && cnt<=r);
    return ret;
}
long long readIntSp(long long l,long long r){
    return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
    return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
    return readString(l,r,'\n');
}
string readStringSp(int l,int r){
    return readString(l,r,' ');
}


bool qr(int x, int y, int a, int b) {
	if(a > 8 || a < 1 || b > 8 || b < 1) return 1;
	if(x == a || y == b || x - a == y - b || x - a == b - y) return 1;
	return 0;
}

void solve() {
    int a, b;
		a = readIntSp(1, 8);
		b = readIntLn(1, 8);
		int ans[9][9];
			for(int p = 1; p <= 8; p++)
			for(int q = 1; q <= 8; q++)
			for(int i = 1; i <= 8; i++)
			for(int j = 1; j <= 8; j++) {
				bool ok = (!(qr(i, j, a, b)));
				ok &= (!(qr(p, q, a, b)));
				for(int k = -1; k < 2; k++)
					for(int l = -1; l < 2; l++) {
						if(!k && !l) continue;
						ok &= (qr(i, j, a + k, b + l) | qr(p, q, a + k, b + l));
					}
				if(ok) {
					
		memset(ans, 0, sizeof(ans));
		ans[a][b] = 1;
					ans[i][j] = 2;
					ans[p][q] = 2;
					if(i == p && j == q) {
					    for(int i = 1; i <= 8; i++) {
			for(int j = 1; j <= 8; j++)
				cout << ans[i][j] << " ";
			cout << "\n";
		}
		return;
					}
					    
				}
			}
		for(int i = 1; i <= 8; i++) {
			for(int j = 1; j <= 8; j++)
				cout << ans[i][j] << " ";
			cout << "\n";
		}
}

int main() {
	int t;
	t = readIntLn(1, 64);
	while(t--) {
		solve();	
	}
	assert(getchar() == -1);
	return 0;
}
Editorialist's code (C++, brute force)
#include "bits/stdc++.h"
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
using ll = long long int;
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

int ans[8][8];

int main()
{
	ios::sync_with_stdio(false); cin.tie(0);

	auto attack = [] (int x, int y, int a, int b) {
		// does a queen at (x, y) attack (a, b) ?
		return x == a or y == b or x+y == a+b or x-y == a-b;
	};

	int t; cin >> t;
	while (t--) {
		int x, y; cin >> x >> y;
		--x, --y;

		int mn = 4;
		for (int i = 0; i < 64; ++i) {
			int x1 = i/8, y1 = i%8;
			if (attack(x1, y1, x, y)) continue;
			for (int j = 0; j < 64; ++j) {
				int x2 = j/8, y2 = j%8;
				if (attack(x2, y2, x, y)) continue;
				for (int k = 0; k < 64; ++k) {
					int x3 = k/8, y3 = k%8;
					if (attack(x3, y3, x, y)) continue;

					int ct = size(set{i, j, k});
					if (mn <= ct) continue;

					bool good = 1;
					for (int dx : {-1, 0, 1}) for (int dy : {-1, 0, 1}) {
						if (dx == 0 and dy == 0) continue;
						int nx = x+dx, ny = y+dy;
						if (nx < 0 or ny < 0 or nx == 8 or ny == 8) continue;

						good &= attack(x1, y1, nx, ny) || attack(x2, y2, nx, ny) || attack(x3, y3, nx, ny);
					}
					if (!good) continue;
					memset(ans, 0, sizeof ans);
					ans[x][y] = 1;
					ans[x1][y1] = ans[x2][y2] = ans[x3][y3] = 2;
					mn = ct;
				}
			}
		}
		for (int i = 0; i < 8; ++i) {
			for (int j = 0; j < 8; ++j) cout << ans[i][j] << " \n"[j == 7];
		}
	}
}
3 Likes

Where to place queens if (a, b) = (2, 2)?

3 Likes

(5,1) and (1,4)

Guys it’s (5, 1) and (1, 4), think a bit before commenting…

3 Likes

Thanks! I could solve it now https://www.codechef.com/viewsolution/72380105

Exactly, if we place at (4,1) and (1,4) the king can still move to (3,3), so for king position=(2,2) queens must be placed at (5,1) and (1,4).

1 Like

true lol.

I am in confusion that now a days contest are being poor quality, i am not even enjoying solving problems even after seeing editorial and yet i am unable to solve.
The same goes to every platform code chef ,codeforces ,leetcode

3 Likes

why this code gives WA? CodeChef

@scorpion101 your code gives WA because your code does not clear the board matrix after each test case. As the values from last test cases still remains on the board.

Run this test cases, and you will get it
2
1 1
8 8

1 Like

What are we actually calculating by doing this?
int ct = size(set{i, j, k});

In my code, that line counts the number of queens placed on the board.

Instead of separately checking configurations of 1 queen/2 queens/3 queens, I did all three at the same time by allowing for overlapping.

Yes got it thanks

thx bro