ISREC - Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Practice

Setter:
Tester: Istvan Nagy
Editorialist: Taranpreet Singh

DIFFICULTY

Easy

PREREQUISITES

Just observation

PROBLEM

Given a grid filled with zeros and ones, check if all ones present in grid form a rectangular subgrid filled with ones or not.

QUICK EXPLANATION

If S denote the set of positions containing ‘1’, then the ones form a rectangle filled with ones if and only if (max_{p \in S}(p.r)-min_{p \in S}(p.r)+1) * (max_{p \in S}(p.c)-min_{p \in S}(p.c)+1) = |S|, p \in S and p.r and p.c denote position (r, c).

EXPLANATION

The ones form a rectangular grid if and only if the rectangle formed by topmost leftmost one and bottom-most rightmost one is completely filled with ones.

Assume for now that all the ones in grid form a rectangle. If S denotes all the positions containing one in grid.
Lemma 1: Among all positions in S, there exists a position p(r, c) such that for all positions q \in S, p.r \leq q.r, p.c \leq q.c. It means that there’s a position containing one, such that all other positions lie to the right/down of that position.
Proof:
WLOG assume p is the position with topmost row, and among those, leftmost position. Hence p.r \leq q.r holds for all positions in S. If position q \in S exists such that q.c < p.c, then position (p.r, q.c) is a position containing zero, and all rectangles containing position p and q has to contain cell (p.r, q.c) which contains zero. Hence the original assumption that all ones form rectangular grid would be contradicted here.

Illustrating above with example,

0000
0010
0110
0000

Here, p = (1, 2), q = (2, 1) and all rectangles containing p and q has to contain position (1, 1) which holds value 0, so rectangular sub-grid cannot exist.

Lemma 2: Among all positions in S, there exists a position p(r, c) such that for all positions q \in S, p.r \geq q.r, p.c \geq q.c. It means that there’s a position containing one, such that all other positions lie to the top/left of that position.

Proof: Almost similar proof applies here as for Lemma 1. The example grid used here would be

0000
0110
0100
0000

and p(2, 1) and q(1, 2), and the position to be included (2, 2)

Hence, based on these two lemmas, if some rectangular sub-grid exists, there exists two positions p, q in S such that all positions in S lie between the rectangle formed by positions p and q as top-left and bottom-right corner of rectangle.

Now, all we need to check is whether this rectangle is filled with ones or not, which can be checked by iterating over grid again.

Alternatively, we can see that for whole sub-grid bounded by these two positions p and q to be filled with ones, the number of ones in grid should be (q.r-p.r+1)*(q.c-p.c+1) = |S|. This works since there are exactly (q.r-p.r+1)*(q.c-p.c+1) cells in this rectangular sub-grid.

  • If |S| > (q.r-p.r+1)*(q.c-p.c+1), then atleast one of the lemma fails and thus the ones don’t form rectangular sub-grid.
  • If |S| < (q.r-p.r+1)*(q.c-p.c+1), then there’s atleast one zero in the sub-grid formed by positions p and q

Hence, we can keep track of minimum and maximum of row and column of positions containing one, and the number of ones and check above condition.

TIME COMPLEXITY

The time complexity is O(N*M) per test case.
The space complexity is O(1) per test case.

SOLUTIONS

Setter's Solution
// #include <format>
#include <climits>
#include <iostream>
#include <fstream>
#include <assert.h>
#include <algorithm>
#include <vector>
#include <set>
#include <string>
#include <queue>
#include <map>

#define pb push_back 

using namespace std;
  
FILE *fp;
ofstream outfile;

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();
        // char g = getc(fp);
        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;
            }
            assert(l<=x && x<=r);
            return x;
        } else {
            assert(false);
        }
    }
}
string readString(int l,int r,char endd){
    string ret="";
    int cnt=0;
    while(true){
        char g=getchar();
        // char g=getc(fp);
        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,' ');
}

const int maxn = 5e2, maxm = 5e2, maxnm = (int)1e6 + (int)5e5;
const int minv = 0, maxv = 1, maxt = 1000;

int main()
{   
    // for(int test = 0; test <= 1; test++){
    //     string in = "/home/daanish/CP/codechef/LearningTeam/Problems/Rectangle/in" + to_string(test) + ".txt";
    //     string out = "/home/daanish/CP/codechef/LearningTeam/Problems/Rectangle/out" + to_string(test) + ".txt";
    //     fp = fopen (in.c_str(), "r");
    //     outfile.open(out.c_str());
        int tnm = 0;
        int t = readIntLn(1, maxt);
        while(t--){
            int n = readIntSp(1, maxn), m = readIntLn(1, maxm); tnm += n * m;
            string s[n];
            int tot = 0;
            for(int i = 0; i < n; i++){
                s[i] = readStringLn(1, m);
                for(int j = 0; j < m; j++)tot += s[i][j] - '0';
            }

            int mini = -1, minminj = -1, minmaxj = -1;
            for(int i = 0; i < n; i++){
                for(int j = 0; j < m; j++){
                    if(s[i][j] == '1'){
                        mini = i; 
                        if(minminj == -1)minminj = j;
                        minmaxj = j;
                    }
                }
                if(mini != -1)break;
            }
            int maxi = -1, maxminj = -1, maxmaxj = -1;
            for(int i = n - 1; i >= 0; i--){
                for(int j = 0; j < m; j++){
                    if(s[i][j] == '1'){
                        maxi = i; 
                        if(maxminj == -1)maxminj = j;
                        maxmaxj = j;
                    }
                }
                if(maxi != -1)break;
            }
            
            bool rs = (tot == (maxi - mini + 1) * (maxmaxj - maxminj + 1));
            if(maxminj != minminj || maxmaxj != minmaxj){
                rs = false;
            }
            for(int i = 0; i < n; i++){
                for(int j = 0; j < m; j++){
                    if(s[i][j] == '1' && (i < mini || i > maxi || j < maxminj || j > maxmaxj)){
                        rs = false; break;
                    }
                }
            }        
            assert(tot > 0);
            string ans = rs ? "YES" : "NO";
            cout << ans << endl;
            // outfile << ans << endl;
        }
        assert(tnm <= maxnm);
        // cout << tnm << endl;
        // outfile.close();
        assert(getchar()==-1);
        // assert(getc(fp)==-1);
    // }
} 
Tester's Solution
#include <iostream>
#include <cassert>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <random>

#ifdef HOME
#include <windows.h>
#endif

#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)

template<class T> bool umin(T& a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool umax(T& a, T b) { return a < b ? (a = b, true) : false; }

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) {
		    assert(cnt > 0);
		    if (is_neg) {
			    x = -x;
		    }
		    assert(l <= x && x <= r);
		    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;
	    }
//   		if(g == '\r')
//   			continue;

	    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, ' ');
}

void calc()
{
    for (int M = 1; M <= 1000; ++M)
    {
	    for (int CM = 1; CM <= 300; ++CM)
	    {
		    if (M * 10000 % (CM * CM) == 0)
		    {
			    printf("%d %d\n", M, CM);
		    }
	    }
    }
}

int main(int argc, char** argv) 
{
#ifdef HOME
    if(IsDebuggerPresent())
    {
	    freopen("../ISREC_0.in", "rb", stdin);
	    freopen("../out.txt", "wb", stdout);
    }
#endif
    int T = readIntLn(1, 1000);
    int sumNM = 0;
    forn (tc, T)
    {
	    int N = readIntSp(1, 500);
	    int M = readIntLn(1, 500);
	    sumNM += N * M;
	    vector<string> w;
	    int minR = N, maxR = 0;
	    int minC = M, maxC = 0;
	    int ones = 0;
	    forn(i, N)
	    {
		    string wi = readStringLn(M, M);
		    w.push_back(wi);
		    forn(j, M)
		    {
			    if (wi[j] == '1')
			    {
				    minR = min(minR, i);
				    maxR = max(maxR, i);

				    minC = min(minC, j);
				    maxC = max(maxC, j);
				    ones++;
			    }
			    else
			    {
				    assert(wi[j] == '0');
			    }
		    }
	    }
	    assert(ones > 0);
	    bool ans = true;
	    fore(i, minR, maxR)
		    fore(j, minC, maxC)
	    {
		    if (w[i][j] != '1')
			    ans = false;
	    }
	    if (ans)
		    printf("YES\n");
	    else
		    printf("NO\n");
    }
    assert(sumNM <= 1'500'000);
    assert(getchar() == -1);
    return 0;
}
Editorialist's Solution
import java.util.*;
import java.io.*;
class ISREC{
    //SOLUTION BEGIN
    void pre() throws Exception{}
    void solve(int TC) throws Exception{
        int N = ni(), M = ni();
        int countOnes = 0;
        int minX = Integer.MAX_VALUE, maxX = Integer.MIN_VALUE;
        int minY = Integer.MAX_VALUE, maxY = Integer.MIN_VALUE;
        for(int i = 0; i< N; i++){
            String S = n();
            for(int j = 0; j< M; j++){
                if(S.charAt(j) == '1'){
                    minX = Math.min(minX, i);
                    maxX = Math.max(maxX, i);
                    minY = Math.min(minY, j);
                    maxY = Math.max(maxY, j);
                    countOnes++;
                }
            }
        }
        pn(countOnes > 0 && countOnes == (maxX-minX+1) * (maxY-minY+1)?"yEs":"nO");
    }
    //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 ISREC().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:

3 Likes

thanks for the fast editorial :smiley:

3 Likes

https://www.codechef.com/viewsolution/43037945

1 Like

@taran_1407 suggestion to remove template code and debugging comments from solution

4 Likes

Very weak test cases for this problem. Even my code which prints “YES” for the following test case got accepted:
1
3 3
101
101
101

Here is the link to my code which got accepted: https://www.codechef.com/viewsolution/43017656

4 Likes

How This input is a Rectangle!
1
3 3
111
000
111

It is Getting YES in accepted Code :-> Solution: 43041708 | CodeChef

1 Like

Wow.

dude, your solution blew my mind, still I can’t capture the idea you tried to put in it. Would you mind explainining it a bit?

2 Likes

Rectangle or any quadrilateral like that has 4 sides… so to detect a vertex I just compared neighboring 3 elements to particular element, so you will see that such patterns are vertices.

10
00

00
10

01
11

01
00

Basically in a square of size 2 x 2, it will have only one 0, three 1 or vice versa.
While these are not…

11
00

Or

00
11

So for a rectangle like shape it will be like this

00000
01110
01110
00000

Total vertex = 4
So it’s a quadrilateral… for any other kind of shape this number would not be 4 so… this is the only case. Where you can write YES… but yeah… maybe this way is not right here…

Also remember to pad you’re matrix with 0’s…
That’s why I took size as (n + 2) × (m + 2)

So it seems tester hadn’t looked into test cases. LOL :rofl:

1 Like

This question also accepts a single cell as a rectangle, a horizontal/vertical line as rectangle. Following testcase outputs all YES when run on an accepted solution:
3
1 1
1
2 2
11
00
2 2
10
10

But this is what expected. All of them should output YES. I guess you’re not clear with the problem statement.

I considered them as point and straight lines, that’s why I thought this shouldn’t be expected.

it’s crazy, I thought it wouldn’t work on test cases like-
00000
11110
11010
11010
11110
00000
It works apparently, thanks bro.

this works as if you think… the middle patch of 0’s would also have vertices… which can be detected as:
11 11
10 01

10 01
11 11
so yeah these would add up too…

#include
#include
#include<bits/stdc++.h>
using namespace std;

int main() {
int t;
cin>>t;
while(t–)
{
int n,m;
cin>>n>>m;
string arr[10000000];
int count=0;
vector<pair<int,int>>v;

    for(int i=0;i<n;i++)
    {
        cin>>arr[i];
        for(int j=0;j<m;j++)
        {
            if(arr[i][j]=='1')
            {
                v.push_back({i,j});
                count++;
               
            }
        }
    }
    int a = v[0].first;
    int b = v[v.size()-1].first;
    int c = v[0].second;
    int d = v[v.size()-1].second;
    int k=(abs(b-a)+1)*(abs(c-d)+1);
    int sum=0;
    
    
    for(int i=0;i<count;i++)
    {
        if((min(a,b)<=v[i].first && max(a,b)>=v[i].first && min(c,d)<=v[i].second && max(c,d)>=v[i].second))
           {
               sum++;
           }
             
    }
    if(sum==count)
    {
        cout<<"YES"<<"\n";
    }
    else
    {
        cout<<"NO"<<"\n";
    }
    
    
    
    
    
    
    
    
}

}

whats wrong in thi solution…i am counting total number of cells between left most and right most…and equating it to total number of 1s…nd making sure all 1s lie between top left most and bottom right most

Weak test cases indeed, I did something bit too complicated but mine did work on all weak cases too, I literally constructed the rectangle with 2d-prefix sums and then detected the rectangle.

void SolveCase(){
    int n,m;
    cin>>n>>m;
    string g[n];
    int cnt1=0;
    vector<int>row(n,0),col(m,0);
    vector<vector<int>>dp(n,vector<int>(m,0));
    int sx = -1;
    int sy = -1;
    for(int i =0;i<n;i++){
        int r =0;
        cin>>g[i];
        for(int j =0;j<m;j++){
            int x = g[i][j]-'0';
            col[j]+=x;
            dp[i][j] = x;
            if(x==1) r+=1;
            if(sx==-1 and sy==-1 and x) {
                sx= i;
                sy = j;
            }
        }
        row[i] = r;
        cnt1+=r;
    }
    int cl = 0;
    int rl = 0;
    for(int i=0;i<n;i++) {
        if(row[i]>0) rl+=1;
    }
    for(int i=0;i<m;i++){
      if(col[i]>0) cl+=1; 
    } 
    bool yes =0;
    if(sx>-1 and sy>-1 and rl>0 and cl>0){
        for(int  i= sx;i<=(sx+rl-1);i++){
            for(int j = sy+1;j<=(sy+cl-1);j++){
                dp[i][j]+=dp[i][j-1];
            }
        }
        for(int i = sx+1;i<=(sx+rl-1);i++){
            for(int j = sy;j<=(sy+cl-1);j++){
                dp[i][j]+=dp[i-1][j];
            }
        }
        yes = (dp[sx][sy]==1 and dp[sx][sy+cl-1]==cl and dp[sx+rl-1][sy]==rl and dp[sx+rl-1][sy+cl-1]==cl*rl);
    }
    Status(yes);
}


3
3 3
101
101
101
NO
3 3
111
000
111
NO
5 5
11110
11010
11010
11110
00000
NO

What are you conveying with this?
The expected answer is NO for all of them.