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.
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.
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