How to do the binary search part of the Parcel problem from Google KickStart

#1

I was trying solving the google kickstart parcel problem i have got the multi source bfs part but in the analytics part there mentioned

Second, we identify all of the squares which have a delivery time greater than  **K**  and then determine if there exists a location that is within a distance of  **K**  to each of these squares. In order to do this efficiently, we note that the manhattan distance has an equivalent formula:

dist((x1, y1), (x2, y2)) = max(abs(x1 + y1 - (x2 + y2)), abs(x1 - y1 - (x2 - y2)))

This formula is based on the fact that for any point, the set of points within a manhattan distance of  **K**  form a square rotated by 45 degrees. The benefit of this formula is that if we fix (x2, y2), the distance will be maximized when x1 + y1 and x1 - y1 are either maximized or minimized.

i didnt get this at all also how can i further binary search the answer Please Help.

#2

For a given K we can find all the squares which have a delivery time greater than K by doing multi source BFS.
Now we have some P points and we have to find a point whose distance from all these P points is <=K. Now let’s iterate through all points (x,y) in R,C grid.
For all p in P manhattan_dist( (x,y) , p) <=K. ------> Condition 1

for a point (x,y) to satisfy the condition 1 the maximum distance from point (x,y) to p <=K.

Let’s take 4 points p1,p2,p3,p4 belonging to P. Where p1 is nearest to (0,0) and p2 is nearest to (R,0) and p3 is nearest to (0,C) and p4 is nearest to (R,C).
Now for all points (x,y) in R*C, the maximum distant point from (x,y) will be one of the above 4 points (i.e p1,p2,p3,p4) . So we check the distance from (x,y) to all those 4 points.
If all those 4 distances is <=K then (x,y) satisfies condition 1.

#3

where will this be used

dist((x1, y1), (x2, y2)) = max(abs(x1 + y1 - (x2 + y2)), abs(x1 - y1 - (x2 - y2)))

#4

I’m not using that

#5

like i have calculated the delivery time of every 0 location from 1 by multisource bfs can you please explain how to approach next i read your answer a number of times but still didnt get it

#6

Did you understand what p1,p2,p3 and p4 are?

#7

They are the four extreme points you have taken to compare every coordinate

But didn’t understood your intuition bro

#8

Yes those 4 points are extreme points and belongs to P.

To get a point (x,y) whose distance from all points in P <=K ,we have to iterate through all points (x,y) and check it’s distance to all p in P <=K.

What my intuition is instead of checking for all p in P it’s enough to check with points p1,p2,p3,p3

#9

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

const int maxN=250;

int arr[maxN][maxN];
int val[maxN][maxN];

int r,c;

bool check(int k)
{
int corners[4][2];
memset(corners,-1,sizeof(corners));

for(int x=0;x<r;x++)
{
    for(int y=0;y<c;y++)
    {
        if(val[x][y]>k)
        {
            if(corners[0][0]==-1)
            {
                corners[0][0]=x;
                corners[0][1]=y;
                
                corners[1][0]=x;
                corners[1][1]=y;
                
                corners[2][0]=x;
                corners[2][1]=y;
                
                corners[3][0]=x;
                corners[3][1]=y;
            }
            else
            {
                if(x+y<corners[0][0]+corners[0][1])
                {
                    corners[0][0]=x;
                    corners[0][1]=y;
                }
                if(-x+y < -corners[1][0]+corners[1][1])
                {
                    corners[1][0]=x;
                    corners[1][1]=y;
                }
                if(x - y < corners[2][0]-corners[2][1])
                {
                    corners[2][0]=x;
                    corners[2][1]=y;
                }
                if(-x - y < -corners[3][0]-corners[3][1])
                {
                    corners[3][0]=x;
                    corners[3][1]=y;
                }
            }
        }
    }
}

if(corners[0][0]==-1)
    return true;

for(int i=0;i<r;i++)
{
    for(int j=0;j<c;j++)
    {
        int cnt=0;
        if(abs(i-corners[0][0])+abs(j-corners[0][1]) <=k )
        {
            cnt++;
        }
        if(abs(i-corners[1][0])+abs(j-corners[1][1]) <=k )
        {
            cnt++;
        }
        if(abs(i-corners[2][0])+abs(j-corners[2][1]) <=k )
        {
            cnt++;
        }
        if(abs(i-corners[3][0])+abs(j-corners[3][1]) <=k )
        {
            cnt++;
        }
        
        if(cnt==4)
            return true;
    }
}

return false;

}

void initialize()
{
memset(val,-1,sizeof(val));

queue<pair<int,int> > q;

for(int i=0;i<r;i++)
{
	for(int j=0;j<c;j++)
	{
		if(arr[i][j])
		{
			val[i][j]=0;
			q.push({i,j});
		}
	}
}

while(!q.empty())
{
	auto pr=q.front();
	q.pop();
	
	int x=pr.first;
	int y=pr.second;
	
	if(x+1<r && val[x+1][y]==-1)
	{
		val[x+1][y]=val[x][y]+1;
		q.push({x+1,y});
	}
	if(x && val[x-1][y]==-1)
	{
		val[x-1][y]=val[x][y]+1;
		q.push({x-1,y});
	}
	if(y+1<c && val[x][y+1]==-1)
	{
		val[x][y+1]=val[x][y]+1;
		q.push({x,y+1});
	}
	if(y && val[x][y-1]==-1)
	{
		val[x][y-1]=val[x][y]+1;
		q.push({x,y-1});
	}
}

}

void solve()
{
cin>>r>>c;

string s;

for(int i=0;i<r;i++)
{
    cin>>s;
    
	for(int j=0;j<c;j++)
		arr[i][j]=s[j]-'0';	
}

initialize();

int lo=0,hi=r*c;
int ans;

while(lo<=hi)
{
    int mid=(lo+hi)/2;
    
    if(check(mid))
    {
        hi=mid-1;
        ans=mid;
    }
    else
    {
        lo=mid+1;
    }
}

cout<<ans<<endl;

}

int main()
{
int t;
cin>>t;

for(int i=1;i<=t;i++)
{
	cout<<"Case #"<<i<<": ";
	solve(); 
}
return 0;

}

1 Like
#10

if(x+y<corners[0][0]+corners[0][1]) what does this denote??

#11

this line is used to find the point nearer to (0,0)