HOLLOW - Editorial

Read it you will never screw again.

2 Likes

Thanks a lot for sharing this!!

Oh I see you have gained a star, congrats on being 5 star cube.

1 Like

Thank you taran for also providing links to get more information about the 2-D prefix sum.

`Help anyone?` My code

1 1 1

2 Likes

`Cheers`

1 Like

Hey there, I think we can also reduce the factor of log2() from time complexity.
Please correct me if I am wrong.

Idea

we can search for a square from a given vertex in increasing order.
i.e. if MAX sq. size of p is founded till now, then it needs not search for a size smaller than p.
I guess it’s time complexity will be o(n*m+min(n,m));

My code
``````#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
#define fast_io ios_base::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL)
#define read(a) ll a; cin >> a;
#define ll long long int
#define endl '\n';

ll aux[1005][1005];
ll mat[1005][1005];
ll sumQuery(int tli, int tlj, int rbi,int rbj)
{
int res = aux[rbi][rbj];
if (tli > 0) res = res - aux[tli-1][rbj];
if (tlj > 0) res = res - aux[rbi][tlj-1];
if (tli > 0 && tlj > 0)  res = res + aux[tli-1][tlj-1];
return res;
}

int main()
{
fast_io;
//“Don’t wish it were easier. Wish you were better.” – Jim Rohn;
while(t--)
{
ll cnt=0;
ll m,n,k; cin>>m>>n>>k;
char c;
FOR(i,0,m-1) FOR(j,0,n-1)
{
cin>>c;
if(c=='1') mat[i][j]=1;
else cnt++,mat[i][j]=0;
aux[i][j]=0;
}
FOR(i,0,n-1)  aux[0][i] = mat[0][i];
FOR(i,1,m-1) FOR(j,0,n-1) aux[i][j] = mat[i][j] + aux[i-1][j];
FOR(i,0,m-1) FOR(j,1,n-1)aux[i][j] += aux[i][j-1];

ll sq_size=0;
FOR(i,0,m-1) FOR(j,0,n-1) FOR(p,sq_size+1,min(n,m))
{
if(i+p-1>m-1 or j+p-1>n-1) break;
ll sum=sumQuery(i,j,i+p-1,j+p-1);
if(sum<=k and p*p<=cnt) sq_size++;
else break;
}
cout<<sq_size<<endl;
}

}
``````

That case is really rare. How many time have you used `long long r = 2e18` or `int r = 2e9`?

Nice Question

Nice question with great explanation

@taran_1407 How to solve this problem, if only swapping of adjacent cells is allowed?

why take a chance
in a contest where there could be a penalty for the wrong submissions

leetcode.com is an interview preparation website. That question is specifically designed so that you know how to calculate mid without overflow.

can anyone help me out in the second test case…

Here is my code…

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