Please provide editorial of Problem G Friend’s meet asap. I want to know how that problem is being solved using Binary Search. If anyone knows that please share your approach. Thanks in advance. 
Binary search on the minimum time taken T and check if you can do in \leq T.
Firstly, you need to transform the input points. Note that if you draw the set of all points which are a certain distance away from a given point, the shape is a 45^o tilted square. Rotate the input points by that angle, the transformation is given by (x,y) \rightarrow (x+y,x-y).
Now, observe that if you had one group, you are going to expand squares simultaneously at the same speed from each point until all have a point in common. The answer would be half the side length you need to give each square. You can observe that the value is just \max(\Delta x,\Delta y) where the values are the maximum coordinate differences (which is given by the highest and lowest, and leftmost and rightmost points). Additionally, notice that this problem is simply the same as checking the minimum size length of a square you need to cover all points.
Now you can imagine that our original problem which has two groups wants us to find the minimum side length you need for 2 squares to cover all the points.
My approach for checking if a certain value worked was to first find the bounding box for the whole set, and then place the two squares at opposite corners (remember that there are two possibilities). Then it’s simply checking if you can place all the points inside either of the two squares (remember to take care of the non-empty condition!).
4 Likes
Please provide the approach of Problem - F…
Shouldn’t the transformation be this (x,y) => ((x-y)/sqrt(2),(x+y)/sqrt(2)).
We are actually not just rotating the points, but the grid lines as well. So now the people are travelling along perpendicular 45^o axes. Imagine a sheet of paper with the drawing, and then rotating the paper itself by 45^o. So the \sqrt{2} factor is cancelled out in the rotated frame of reference, which makes sense when you think about it. It’s simply a change of perspective.
I understood it like this. Can you please correct me if i am wrong or understood something wrong!
As we are rotating the axes, the co-ordinate (x,y) in the new rotated system will be ((x-y)/sqrt(2),(x+y)/sqrt(2)). Now, if we scale up our new co-ordinates by multiplying them by a factor of sqrt(2) our bounding minimum square length’s will also get multiplied by that.
So, let L’ is the found minimum length. Now , we know that L’=sqrt(2)L0( actual side length of minimum bounding square)
=> L0=L’/sqrt(2).
Now, the max. dist one may have to cover in this square will be L0/sqrt(2)= (L’/sqrt(2))/sqrt(2)= L’/2.