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
- take all points from all possible line segments of A and B
- sort all of them
- select the unique points
- assign them appropriate values fr eg set of pts=[1,6,8,10], corresp values=[1,2,3,4]
- 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
- 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)
- perform prefix sum
- 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.
What about this test case-
1 1 1
2 Likes
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