CHECKMATE - Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Practice

Setter: Daanish Mahajan
Tester: Abhinav sharma
Editorialist: Taranpreet Singh

DIFFICULTY

Simple

PREREQUISITES

None

PROBLEM

Given the positions with exactly two black rooks and one white king on an 8 \times 8 chessboard with the white king not in check and black to move, determine if it is possible to checkmate the white king in one move or not.

QUICK EXPLANATION

There are only four candidate moves, which can result in a checkmate. Determine if there’s one of them, which is possible as well as results in checkmate. If there’s such a move, then the answer is yes.

EXPLANATION

There are multiple solutions to this problem. One is based on several cases, based on observations

  • The king must either be in topmost or bottom-most row, or leftmost or rightmost column, Otherwise it’s impossible to checkmate.
  • WLOG if the king is in the topmost row, the two rooks must not be in the same column, one of them in the 2nd topmost row, and the other rook moves to the topmost row as the move.
  • The king shouldn’t be able to capture either of the two rooks.

The above solution can be written with a series of conditional statements. I have a better solution. Let the computer do the hard work. Let us try all possible moves for the rooks, and for each of them, determine if the current position is a checkmate or not.

Check if a given position is checkmate

Assume we are given the position of both rooks and king, and we need to check if the current king is checkmated or not. We can simply iterate on the at most 9 cells reachable by the king, and if each of them is attacked by at least one rook, and no rook can be captured by the king, the king is checkmated.

Checking if some cell (x, y) is attacked by a rook in cell (r, c) is simply checking if it has same row or column, i.e. x = r or y = c holds.

Checking if king at position (x, y) can capture rook at cell (r, c) is simply checking if max(|r-x|, |c-y|) \leq 1.

Now, since we know how to check both conditions for checkmate, we can easily determine in a position with two black rooks and a white king if the white king is checkmated or not.

All possible moves for rooks

For each rook, at most 7 positions in the same row, and 7 cells in the same column are possible, Hence 14 possible moves for the first rook, and at most 14 possible moves for the second rook. So we can have at most 28 cases to consider.

But, since we need to checkmate the king, the rook being moved must either be in the same row as the king or the same column as the king. So there are only 2 moves to consider for each rook, Hence we are left with 4 possible candidate moves.

For these moves, we need to check if it is possible to make that move, and whether it leads to checkmate or not. The second part is done, now the first part.

Check if a move is possible

Let’s assume you have the position of one rook, and the other rook’s start and end position. You need to determine if it is possible to move the second rook from start to end position.

The move is not possible only when the first rook is on the path from the start and end position of the second rook, which can be easily checked.

My solution uses exactly the same idea, with readable functions doing each of the above tasks, feel free to refer to that if needed.

TIME COMPLEXITY

The time complexity is O(1) per test case

SOLUTIONS

Setter's Solution
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define pb push_back
#define mp make_pair
#define F first
#define S second
ostream& operator<<(ostream& os, pii p)
{
    os << "(" << p.F << ", " << p.S << ")";
    return os;
}
bool mid(int z, int x, int y){
    if(x > y)swap(x, y);
    return z >= x && z <= y;
}
bool chk(pii k, pii r1, pii r2){
    for(int i = -1; i <= 1; i++){
        for(int j = -1; j <= 1; j++){
            pii kn = {k.F + i, k.S + j};
            if(kn.F <= 0 || kn.F > 8 || kn.S <= 0 || kn.S > 8 || kn == k)continue;
            if(kn == r1 || kn == r2)return false;
		    // cout << "HI" << kn << " " << r1 << " " << r2 << endl;
            if(!(kn.F == r1.F || kn.S == r1.S || kn.F == r2.F || kn.S == r2.S))return false;
        }
    }return true;
}
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int t; cin >> t;
    while(t--){
	    pii k, r1, r2;
	    cin >> k.F >> k.S;
	    cin >> r1.F >> r1.S;
	    cin >> r2.F >> r2.S;
	    bool ans = false;
	    if(!(r1.S == r2.S && mid(r2.F, k.F, r1.F)))ans |= chk(k, {k.F, r1.S}, r2);
	    if(!(r1.F == r2.F && mid(r2.S, k.S, r1.S)))ans |= chk(k, {r1.F, k.S}, r2);
	    if(!(r1.S == r2.S && mid(r1.F, k.F, r2.F)))ans |= chk(k, r1, {k.F, r2.S});
	    if(!(r1.F == r2.F && mid(r1.S, k.S, r2.S)))ans |= chk(k, r1, {r2.F, k.S});
	    cout << (ans ? "YeS" : "No") << endl;
    }
    return 0;
}
Tester's Solution
#include <bits/stdc++.h>
using namespace std;
 
 
/*
------------------------Input Checker----------------------------------
*/
 
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,' ');
}
 
 
/*
------------------------Main code starts here----------------------------------
*/
 
const int MAX_T = 160000;
const int MAX_N = 1e6+5;
const int MAX_SUM_LEN = 1e5;
 
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
 
int sum_len = 0;
int max_n = 0;
int yess = 0;
int nos = 0;
int total_ops = 0;
 
int n;

bool chk(int x_k, int y_k, int x_1, int y_1, int x_2, int y_2){
    bool f=1;
    for(int i=x_k-1; i<=x_k+1; i++){
        for(int j=y_k-1; j<=y_k+1; j++){
            if(i < 1 || i > 8 || j < 1 || j > 8) continue;
            bool tmp = 0;
            if(i == x_1 || i == x_2 || j == y_1 || j == y_2) tmp=1;
            if(x_1 != x_2 && y_1 != y_2){
                if(i == x_1 && j == y_1) tmp = 0;
                if(i == x_2 && j == y_2) tmp = 0;
                   
            }
            f&=tmp;
        }
    }
    return f;
}
 
int solve()
{   
  int x_k, y_k, x_1, y_1, x_2, y_2;
  x_k = readIntSp(1,8);
  y_k = readIntLn(1,8);
  x_1 = readIntSp(1,8);
  y_1 = readIntLn(1,8);
  x_2 = readIntSp(1,8);
  y_2 = readIntLn(1,8);

  assert(x_k!=x_1 && x_k!=x_2 && y_k!=y_1 && y_k!=y_2);

  for(int i=1; i<=8; i++){
    if(!(y_2 == y_1 && (i-x_2)*(x_1-x_2) <= 0) && chk(x_k, y_k, i, y_1, x_2, y_2)) return 1;
    if(!(x_2 == x_1 && (i-y_2)*(y_1-y_2) <= 0) && chk(x_k, y_k, x_1, i, x_2, y_2)) return 1;
    if(!(y_2 == y_1 && (i-x_1)*(x_2-x_1) <= 0) && chk(x_k, y_k, x_1, y_1, i, y_2)) return 1;
    if(!(x_2 == x_1 && (i-y_1)*(y_2-y_1) <= 0) && chk(x_k, y_k, x_1, y_1, x_2, i)) return 1;
  }

  return 0;


}
 
signed main()
{

    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r" , stdin);
    freopen("output.txt", "w" , stdout);
    #endif
    fast;
    
    int t = 1;
    
    t = readIntLn(1,MAX_T);
    
    for(int i=1;i<=t;i++)
    {    
       int res = solve();
       if(res) yess++;
       else nos++;
       cout<<(res?"YeS" : "nO")<<'\n';
    }
    
    assert(getchar() == -1);
 
    cerr<<"SUCCESS\n";
    cerr<<"Tests : " << t << '\n';
    //cerr<<"Sum of lengths : " << sum_len << '\n';
    // cerr<<"Maximum length : " << max_n << '\n';
    // cerr<<"Total operations : " << total_ops << '\n';
    cerr<<"Answered yes : " << yess << '\n';
    cerr<<"Answered no : " << nos << '\n';
}
Editorialist's Solution
import java.util.*;
import java.io.*;
class CHECKMATE{
    //SOLUTION BEGIN
    void pre() throws Exception{}
    void solve(int TC) throws Exception{
        int Ck = ni(), Rk = ni(), C1 = ni(), R1 = ni(), C2 = ni(), R2 = ni();
        
        boolean yes = false;
        yes |= canMove(R1, C1, Rk, C1, R2, C2) && checkmate(Rk, Ck, Rk, C1, R2, C2);
        yes |= canMove(R1, C1, R1, Ck, R2, C2) && checkmate(Rk, Ck, R1, Ck, R2, C2);
        yes |= canMove(R2, C2, Rk, C2, R1, C1) && checkmate(Rk, Ck, R1, C1, Rk, C2);
        yes |= canMove(R2, C2, R2, Ck, R1, C1) && checkmate(Rk, Ck, R1, C1, R2, Ck);
        
        pn(yes?"YES":"NO");
    }
    boolean canMove(int stR, int stC, int enR, int enC, int R, int C){
        if(stR != enR && stC != enC)return false;
        if(stR == enR && stC == enC)return true;

        if(stC == enC)
            return C != stC || R < Math.min(stR, enR) || R > Math.max(stR, enR); 
        else
            return R != stR || C < Math.min(stC, enC) || C > Math.max(stC, enC);
    }
    boolean checkmate(int Rk, int Ck, int R1, int C1, int R2, int C2){
        for(int dr = -1; dr <= 1; dr++)
            for(int dc = -1; dc <= 1; dc++){
                int r = Rk+dr, c = Ck+dc;
                if(Math.min(r, c) < 1 || Math.max(r, c) > 8)continue;
                if(r == R1 && c == C1)return false; //King capture rook at (R1, C1)
                if(r == R2 && c == C2)return false; //King capture rook at (R2, C2)
                if(r != R1 && c != C1 && r != R2 && c != C2)return false; //King can move to (r, c)
            }
        return true;
    }
    //SOLUTION END
    void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
    static boolean multipleTC = true;
    FastReader in;PrintWriter out;
    void run() throws Exception{
        in = new FastReader();
        out = new PrintWriter(System.out);
        //Solution Credits: Taranpreet Singh
        int T = (multipleTC)?ni():1;
        pre();for(int t = 1; t<= T; t++)solve(t);
        out.flush();
        out.close();
    }
    public static void main(String[] args) throws Exception{
        new CHECKMATE().run();
    }
    int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
    void p(Object o){out.print(o);}
    void pn(Object o){out.println(o);}
    void pni(Object o){out.println(o);out.flush();}
    String n()throws Exception{return in.next();}
    String nln()throws Exception{return in.nextLine();}
    int ni()throws Exception{return Integer.parseInt(in.next());}
    long nl()throws Exception{return Long.parseLong(in.next());}
    double nd()throws Exception{return Double.parseDouble(in.next());}

    class FastReader{
        BufferedReader br;
        StringTokenizer st;
        public FastReader(){
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        public FastReader(String s) throws Exception{
            br = new BufferedReader(new FileReader(s));
        }

        String next() throws Exception{
            while (st == null || !st.hasMoreElements()){
                try{
                    st = new StringTokenizer(br.readLine());
                }catch (IOException  e){
                    throw new Exception(e.toString());
                }
            }
            return st.nextToken();
        }

        String nextLine() throws Exception{
            String str = "";
            try{   
                str = br.readLine();
            }catch (IOException e){
                throw new Exception(e.toString());
            }  
            return str;
        }
    }
}

Feel free to share your approach. Suggestions are welcomed as always. :slight_smile: