# HOLLOW - Editorial

such things happen pal, I remember running a binary search in the opposite direction(reversing conditions of l=mid+1 and r=mid-1) on multiple occasions

2 Likes

So is this the generic binary search template you use for all binary search problems or you manipulate the <= or < ,r=m-1 or r=m etc… according to the problem ?

1 Like

i don’t use any templates, i write one according to the problem

2 Likes

Can someone explain the last problem solution. I found no editorial for it.

1. take all points from all possible line segments of A and B
2. sort all of them
3. select the unique points
4. assign them appropriate values fr eg set of pts=[1,6,8,10], corresp values=[1,2,3,4]
5. do the same thing u do when u have to add +1 to a segment, ie mark starting indices as +1, ending as -1, and perform cumulative sum
6. any point on this newly formed array now indicates number of lines moving from pt(i) to pt(i+1), so the value it can contribute will be [pt(i+1)-pt(i)]*(number of lines)
7. perform prefix sum
8. find value for all ranges of B in O(1) using the prefix sum
The total sum is your answer. Time complexity is NlogN.

The code.

1 Like
1 Like

Oh, so sorry that I was not able to find the editorial.

// I AM TRYING TO DEBUGGING MY CODE FROM LAST 2 HRS BUT NOT ABLE THAT WHERE I AM WRONG .PLEASE SOMEONE HELP ME! THNX


import java.util.*;
import java.lang.*;

public class Main
{
static int[][] arr ;
static int[][] dp ;
static int n,m,k,c0,c1 ;

public static boolean check(int a)
{

if(a*a > c0)return false  ;

for(int i = 1 ; i <= n-a+1 ;i++)
{
for(int j = 1 ; j <= m-a+1 ;j++)
{
int x = i+a-1 ;int y = j+a-1 ;

int val1 = dp[x][y] ;
int val2  = dp[i-1][j-1] ;
int val3  = dp[i-1][y] ;
int val4  = dp[x][j-1] ;

int val = val1 -val3-val4+val2  ;

val =  (a*a) -val ;

if(val <= k)return true  ;

}
}

return false  ;

}

public static void solve()
{

Scanner scn = new Scanner(System.in) ;

int testcase = 1;
testcase = scn.nextInt() ;
for(int testcases =1  ; testcases <= testcase ;testcases++)
{

n= scn.nextInt() ; m= scn.nextInt() ; k= scn.nextInt() ;

arr = new int[n+10][m+10] ;dp = new int[n+10][m+10] ;

for(int i = 1 ; i <= n ;i++)
{
String s = scn.next() ;
s= "%" + s ;

for(int j = 1 ; j <= m ;j++)
{
if(s.charAt(j) == '1')arr[i][j] = 1;
else arr[i][j] = 0 ;

if(arr[i][j] == 0)c0++ ;
else c1++ ;

}

}

if(arr[1][1] == 0)dp[1][1] =1 ;
else dp[1][1] =0;

for(int j = 2 ; j <= m;j++)
{
dp[1][j] = dp[1][j-1] ;

if(arr[1][j] == 0)dp[1][j]++ ;
}

for(int i = 2 ; i <= n;i++)
{
dp[i][1] = dp[i-1][1] ;

if(arr[i][1] == 0)dp[i][1]++ ;
}

for(int i = 2 ; i <= n ; i++)
{
for(int j = 2; j <= m ;j++)
{

dp[i][j] = dp[i-1][j] + dp[i][j-1] -dp[i-1][j-1] ;

if(arr[i][j] == 0)dp[i][j]++ ;

}

}

int s = 0 ;int e  = Math.min(n,m) ;

int ans = 0 ;

while(s <= e)
{
int m = (s+e)/2 ;

if(check(m))
{
ans = m ;
s=m+1 ;
}

else{

e=m-1  ;
}

}

System.out.println(ans) ;

}

}

public static void main (String[] args) throws java.lang.Exception
{

solve() ;

}

}


IT CAN LOOK A BIT LARGE AT FIRST GLANCE BUT IT IS SAME ,CHECK Fn CHECKING THE CONDITION AND REST JUST PREFIX CALCULATION .

For calculating mid. The best practice is to use mid = r-l / 2 + l
This will prevent overflow in case of l+r

2 Likes

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

What about this test case-
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;
read(t);
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