GOODGRID - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Div-2 Contest
Div-1 Contest

Author: Utkarsh Gupta
Tester: Rahul Dugar
Editorialist: Mohammed Ehab

DIFFICULTY:

EASY

PREREQUISITES:

None

PROBLEM:

There’s an N \times N grid. We call an element good if it’s the maximum in its column and the minimum in its row. Given N and X, is there an N \times N grid with X good elements?

QUICK EXPLANATION:

The good elements form a rectangle, so the answer is yes if and only if X can be written as a*b with a,b \le N.

EXPLANATION:

Let’s look at any good element G. Suppose there’s an element A that’s strictly greater than G in its row. Then, I claim there can’t be any good elements in A's column. Look at the following picture:

codechef1

Suppose C is a good element in A's column, and suppose B is the element in the intersection of G's column and C's row, then the 4 inequalities I wrote must hold. However, they’re inconsistent with each other. On one hand, we have C \le B \le G. On the other, we have C \ge A > G. So that’s why you can’t have a good element in A's column. Similarly, if you have an element A in G's column that’s strictly smaller than G, you can’t have a good element in A's row.

So that means, if we have another good element C, we must have A=B=C=G, or we’ll end up with inconsistent inequalities. In words, the intersections of rows and columns of good elements are also good elements. So that means the good elements form some sort of rectangle. Sure, it has gaps in it, but you can rearrange the rows and columns of the grid to make it a contiguous rectangle. Let me draw you a picture of the grid after rearranging:

codechef2

Since the good elements for a rectangle with both dimensions limited by N, the answer is yes if and only if X can be written as a*b with a,b \le N

SOLUTIONS:

Editorialist's Solution 
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int t;
    scanf("%d",&t);
    while (t--)
    {
        int n,x;
        scanf("%d%d",&n,&x);
        bool ok=0;
        for (int a=1;a<=n;a++)
        ok|=(x%a==0 && x/a<=n);
        puts(ok? "Yes":"No");
    }
}

VIDEO EDITORIAL:

5 Likes