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. 
