RECHEND - Editorial

PROBLEM LINK:

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

Author: Sandeep V
Tester: Danny Mittal
Editorialist: Nishank Suresh

DIFFICULTY:

Easy

PREREQUISITES:

None

PROBLEM:

There is a square grid of size N\times N, where exactly N cells are blocked. Further, they are distributed such that there is exactly one blocked cell in every row and every column.
Is it possible to move from \left(1, 1\right) to \left(N, N\right) by taking only rightward and downward steps, without passing through any blocked cell?

QUICK EXPLANATION:

The answer is Yes if and only if no diagonal (with constant i+j) is filled with blocked cells.

EXPLANATION:

Drawing out a few examples on paper will likely give you the idea to check whether a diagonal is completely blocked.

This is both a necessary and a sufficient condition for a path to exist.

For convenience, the diagonal consisting of cells \left(i, j\right) such that i + j = c will be called diagonal c.

Proof of necessity

Suppose there is a path from \left(1, 1\right) to \left(N, N\right).
\left(1, 1\right) lies on diagonal 2, and each step we take, whether rightward or downward, moves us from diagonal i to diagonal i+1. As a result, we pass through exactly one square in each diagonal.
The only way such a path can exist is if every diagonal has at least one unblocked cell, making this a necessary condition.

Proof of sufficiency

Suppose that every diagonal has at least one unblocked cell. We will construct a path from \left(1, 1\right) to \left(N, N\right).

There is exactly one blocked cell in the first row - let it be \left(1, x\right) where x > 1. Let k be the smallest integer such that cells \left(1, x\right), \left(2, x-1\right), \dots, \left(k, x+1-k\right) are all blocked but cell \left(k+1, x-k\right) is not blocked.
This diagonal has at least one unblocked cell by assumption, so we know for a fact that k < x, i.e, x - k > 0.
Now do the following:
Move right from \left(1, 1\right) to \left(1, x-k\right). All these cells are not blocked because the only blocked cell in row 1 is in column x.
Then, move down to \left(k+1, x-k\right). Again, all these cells are unblocked because the cells blocked in rows 2, 3, \dots, k occur in columns after x-k, and \left(k+1, x-k\right) is unblocked by assumption.
Next, move right to \left(k+1, x\right). The cells along this path are unblocked because the blocked cells in each of these columns are above the path.
Finally, move down to \left(x, x\right).

We are now at position (x, x). Further, note that cells (x, x), (x+1, x), \dots, (N, x) are all unblocked because (1, x) is blocked.
We can now move from (x, x) to (N, N) via a similar constructive process.
The last row has exactly one blocked cell - let this be (N, y). Clearly, y = x is not possible.

  • If y < x, we can simply move down to (N, x) and then right to (N, N), with all intermediate cells being unblocked.
  • Suppose y > x. Let r be the smallest integer such that cells \left(N, y\right), \left(N-1, y+1\right), \dots, \left(N-r, y+r\right) are all blocked but cell \left(N-r-1, y+r+1\right) is not blocked.
    Since all diagonals of the grid have an unblocked cell, such a r does exist, and will be < N-y.
    Now do the following:
    Move down to (N-r-1, x).
    Next, move right to (N-r-1, y+r+1) - all intermediate cells are unblocked because the blocked cells in these columns are strictly below this path.
    Next, move down to (N, y+r+1) - all intermediate cells are unblocked because the blocked cells in these rows are strictly to the left of this path.
    Finally, move right to (N, N) and we are done.

All that remains is to check whether some diagonal is indeed blocked. A simple way to do this is to maintain a frequency table of x+y for every cell \left(x, y\right) in the input, and then iterate over every diagonal x+y and check whether freq[x+y] equals the length of that diagonal.

TIME COMPLEXITY:

\mathcal{O}(N\log N) or \mathcal{O}(N) per test.

CODE:

Setter (Python)
import sys
input=sys.stdin.readline
t=int(input())
for _ in range(t):
    n=int(input())
    c=dict()
    for i in range(n):
        a,b=map(int,input().split())
        if(a+b in c):
            c[a+b]+=1
        else:
            c[a+b]=1
    fl=1
    for i in range(2,n+1):
        if(i in c):
            if(c[i]==i-1):
                fl=0
                break
    j=n+1
    k=n
    for i in range(n-1):
        if(j in c):
            if(c[j]==k):
                fl=0
                break
        j+=1
        k-=1
        #print(j,k)
    #print(c)
    if(fl==0):
        print("NO")
    else:
        print("YES")
Tester (Kotlin)
import java.io.BufferedInputStream

fun main(omkar: Array<String>) {
    val jin = FastScanner()
    repeat(jin.nextInt(1000)) {
        val n = jin.nextInt(1000000)
        val ys = IntArray(n + 1)
        repeat(n) {
            val x = jin.nextInt(n, false)
            val y = jin.nextInt(n)
            ys[x] = y
        }
        if (ys.toSet().size != n + 1) {
            throw IllegalArgumentException("not all distinct y")
        }
        if ((1..n).any { ys[it] == 0 }) {
            throw IllegalArgumentException("not all distinct x")
        }
        if (ys[1] == 1 || ys[n] == n) {
            throw IllegalArgumentException("start and/or finish blocked")
        }
        println(if ((1..ys[1]).all { it + ys[it] == 1 + ys[1] } || (ys[n]..n).all { it + ys[it] == n + ys[n] }) "nO" else "yEs")
    }
}

class FastScanner {
    private val BS = 1 shl 16
    private val NC = 0.toChar()
    private val buf = ByteArray(BS)
    private var bId = 0
    private var size = 0
    private var c = NC
    private var `in`: BufferedInputStream? = null

    constructor() {
        `in` = BufferedInputStream(System.`in`, BS)
    }

    private val char: Char
        private get() {
            while (bId == size) {
                size = try {
                    `in`!!.read(buf)
                } catch (e: Exception) {
                    return NC
                }
                if (size == -1) return NC
                bId = 0
            }
            return buf[bId++].toChar()
        }

    fun nextInt(): Int {
        var neg = false
        if (c == NC) c = char
        while (c < '0' || c > '9') {
            if (c == '-') neg = true
            c = char
        }
        var res = 0
        while (c >= '0' && c <= '9') {
            res = (res shl 3) + (res shl 1) + (c - '0')
            c = char
        }
        return if (neg) -res else res
    }

    fun nextInt(unused1: Int, unused2: Boolean = true) = nextInt()

    fun nextInt(unused1: Int, unused2: Int, unused3: Boolean = true) = nextInt()
}
Editorialist (C++)
#include "bits/stdc++.h"
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,mmx,avx,avx2")
using namespace std;
using ll = long long int;
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

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

    int t; cin >> t;
    while (t--) {
        int n; cin >> n;
        vector<array<int, 2>> v(n);
        for (auto &[x, y] : v)
            cin >> x >> y;
        sort(begin(v), end(v));
        int lst = 0;
        for (int i = 1; i < n; ++i) {
            if (v[i][1] == v[i-1][1] - 1) lst = i;
            else break;
        }
        if (v[lst][1] == 1) {
            cout << "No\n";
            continue;
        }

        reverse(begin(v), end(v));
        lst = 0;
        for (int i = 1; i < n; ++i) {
            if (v[i][1] == v[i-1][1] + 1) lst = i;
            else break;
        }
        if (v[lst][1] == n) {
            cout << "No\n";
            continue;
        }
        cout << "Yes\n";
    }
}
7 Likes

Can anyone (author, tester) show me the test case generator code for this problem?
As I was trying to debug my solution by comparing the output from the brute approach and my efficient approach but was not able to write the test case generator code.

Easier implementation:

void solve() {
  int n;
  cin >> n;
  int x, y;
  vi cnt(2 * n + 1);
  f0(i, n) {
    cin >> x >> y;
    cnt[x + y]++;
  }
  for (int i = 2; i <= n; i++) if (cnt[i] == i - 1) {
    cout << "No\n";
    return;
  }
  int c = n;
  for (int i = n + 1; i <= 2 * n; i++, c--) {
    if (cnt[i] == c) {
      cout << "No\n";
      return;
    }
  }
 cout << "Yes\n";
}
4 Likes

Just give your code let me check and tell it for you!

1 Like

Your proof of sufficiency has a gap. In the [x,n]×[x,n] square you arrive at after the first step, there may be no blocked cell at the top row. In this case, it’s not clear how you continue your path.

1 Like

Can anyone find a counterexample for my approach., viz

  • Even I noticed that there must be a diagonal (with slope 45\degree).

  • Given that there are exactly N blocked cells, there is exactly one blocked cell in every row and every column.

  • With this, the problem is divided into the following three ways.

    1. Above
      There is a diagonal strictly above the diagonal (x + y = N + 1). There can be other blocked cells too.

    2. on
      There is a diagonal along the cells satisfying (x + y = N + 1).

    3. Below
      There is a diagonal below the diagonal (x + y = N + 1). There can be other blocked cells too.

  • Notice the cells encircled in red. I call them the start cells. These are the cells that lie on either or both of the lines X = 1 and Y = N.

  • My claim is that there are no more than 2 such cells (that lie on either or both of the lines X = 1 and Y = N).

  • My goal is to find all such cells (there are no more than two, so four variables should be enough).

  • Now, once found, I will keep reducing the Y coordinate and increase the X coordinate while X <= N and Y >= 1. While performing these operations, I will check if cells with those coordinates are blocked or not.

  • If this loop ends without breaking, then we have found a diagonal that blocks the path from (1, 1) to (N, N). Based on which I am outputting “YES” or “NO”.

On submitting the solution, the verdict was \color{red}\text{WA}. Here’s my code.

CPP Code
void solve() {
	int N = 0;
	cin >> N;
	set<pair<int, int>> my_set;

	int line_x1 = -1, line_y1 = -1;
	int line_x2 = -1, line_y2 = -1;
	// These four variables keep track of blocked
	// Cells that lie on either or both of the lines
	// X = 1 and Y = N

	for(int i = 0; i < N; i++) {
		pair<int, int> p;
		cin >> p.first >> p.second;
		if(p.first == 1) {
			// We found a cell that lies
			// on the line X = 1
			line_x1 = 1;
			line_y1 = p.second;
		}
		if(p.second == N) {
			// We found a cell that lies
			// on the line Y = N
			line_x2 = p.first;
			line_y2 = N;
		}
		my_set.insert(p);
	}

	bool flag = true;

	if(line_x1 == 1) {
	// Check if there is a diagonal of type 1
		while(line_y1 > 0) {
			if(my_set.find(make_pair(line_x1, line_y1)) == my_set.end()) {
				flag = false;
				break;
			}
			line_x1++;
			line_y1--;
		}
	} 

	if(line_y2 == N) {
	// Check if there is a diagonal of type 3
		while(line_x2 <= N) {
			if(my_set.find(make_pair(line_x2, line_y2)) == my_set.end()) {
				flag = false;
				break;
			}
			line_x2++;
			line_y2--;
		}
	}
	// Diagonal of type 2 is handled in both of them.

	cout << (flag ? "NO" : "YES") << '\n';
}

Any help is greatly appreciated. Thanks in advance.

Nice problem. I couldn’t come up with the sufficiency idea during the contest. Had to rely on proof by AC.

Also @iceknight1093 you mention r being the smallest integer for the step after reaching (x,x) and y > x. I don’t see anywhere r being used, a typo perhaps?

Good catch!
I’ve updated the proof to not require induction and instead explicitly construct the remaining part of the path, let me know if it’s ok now.

Ah, I meant to use r so as to make it clear that it’s different from the k of the first part and then totally forgot about it. Thanks for noticing, I’ll change it now.

Can anyone please tell me which case did i miss . I have implemented the same concept
https://www.codechef.com/viewsolution/53070001

i dont think so , maybe the test cases are weak but imagine this :
N = 5
points : (1, 2) , (2, 2) , (3, 1) [lets say we only have these 3 points for now]

the matrix will look like :

1 0 1 1 1
1 0 1 1 1
0 1 1 1 1
1 1 1 1 1
1 1 1 1 1

here we can’t move forward but your ans will pass yes

Your idea is correct, the implementation has a small mistake.
Suppose the cells (1, 2) and (2, 1) are blocked, and (N-1, N) is blocked but (N, N-1) is not (assume N large enough, say N = 10).

The lower diagonal being not blocked will set flag = false at the end, which is not what you want.

2 Likes

That code is correct, and is in fact just an implementation of the last line mentioned in the editorial.

The test you gave is not valid because there are 2 blocked cells in the second column, while the input constraints guarantee that this cannot happen.

ohhh right! i didn’t see the Xi≠Xj and Yi≠Yj
due this tc i didn’t submit this approach , i had this :cry:

Your Code will Fail for This—>
5
1 2
2 3
3 4
4 4
5 4

It will give Yes but answer should be No

The problem has special constraint: “Each row contains exactly one block and each column contains exactly one block”.
So your test case is invalid.

Python Solution with comment for better understanding.

import sys 
from collections import defaultdict 


ins = lambda: sys.stdin.readline().strip()
inarr =  lambda s:  list(map(s, sys.stdin.readline().strip().split()))

outs = lambda n : sys.stdout.write(str(n) + "\n") 
outarr = lambda li : sys.stdout.write(" ".join(map(str,li)) + "\n") 

# In lambda we do not need to use return keyword
gcd = lambda a,b: b if a == 0 else gcd(b%a, a)
    
    
def solve():
    n = int(ins())
    d = defaultdict(int)
    
    
    for __ in range(n):
        
        x, y = inarr(int)
        
        d[x+y] += 1 
        
    # till 1,n diagoanl size will increase with sum
    for i in range(2,n+1):
        
        if d[i] == i-1:
            outs('NO')
            return 
        
    # after that, diagonal size will increase with sum 
    diagonal_size = n
    for i in range(n+1, 2*n):
        
        if d[i] == diagonal_size:
            print('NO')
            return 
        
        diagonal_size -= 1 
        
        
    
    outs('YES')
    

t = int(ins())

for _ in range(t):
    
    solve()
    

        
        

Your test case is wrong. You can not put 2 block box in same row / col. That is given in the question

May I request to get test-cases to fail my code here? I have tried all edge cases for N = 4 and N=5 and they all pass this code. But submission gives WA

Thanks in advance.

P.S. - The solution from tester(Danny Mittal) is amazing.

 // Kotlin
 fun solve(inputRead: InputReader, out: PrintWriter) {
        // read N
        var n = inputRead.nextInt()

        // get x-y pairs
        var blocks = List(n){ Pair(inputRead.nextInt(), inputRead.nextInt()) }

       // sort by x, so that processing starts from row 1, row 2, and so on
        blocks = blocks.sortedBy { it.first }

       // start with second row
        var index = 1

        var col = 0

        // assume it is possible to block a diagonal
        var possible = true

       // if blocking a diagonal is possible and we reached 1 column, diagonal is fully blocked
        // if we reached 1 column without blocking, continue
        // if the blocks are still there to be processed, continue
        while((col > 1 || !possible) && index < blocks.size) {
            // get the column of this row
            col = blocks[index].second
            // if col is **NOT** 1 less than previous, blocking is not possible
            if(col + 1 != blocks[index - 1].second) {
                possible = false
            }
            // however if we find Nth column again, it may be possible to block the diagonal if we keep searching
            // it will Not be last row and next x-y pair will be processed for col+1 rule
            if(col == n) possible = true

            // go to next x-y pair
            index += 1
        }
       
        // if blocking is possible, output NO, else YES
        out.println(if(possible) "NO" else "YES")

    }

:disappointed_relieved:

So stupid of me. Thanks a lot, bro. Got that AC.