TRAVELAL - Editorial

editorial
, , ,
1

PROBLEM LINK -

Practice

Contest

Author and Editoriallist - AmirReza PoorAkhavan

Tester - MohammadSina Pakseresht

Second Tester - Shayan CheshmJahan

DIFFICULTY –

PREREQUISITES –

Binary-search.

EXPLANATION –

Let’s use binary-search, now the problem is how to check if it’s possible for some fixed D to start at some special point and visit each of the other special points, directly or through other special points.

Let’s build a graph and for each pair of vertices put an edge between them if and only if |x_i - x_j| + |y_i - y_j| \geq D. Now, Check if it’s connected. For the first subtask, it’s really easy, just build the graph naively and check if it’s connected.

Let’s check which points are connected to point (X, Y). You can see that (P, Q) is connected to (X, Y) if at least one of the below conditions satisfied:

  • P + Q \geq X + Y + D \Rightarrow P - X + Q - Y \geq D \Rightarrow |P - X| + |Q - Y| \geq D
  • P + Q \leq X + Y - D \Rightarrow P - X + Q - Y \leq -D \Rightarrow |P - X| + |Q - Y| \geq D
  • P - Q \geq X - Y + D \Rightarrow P - Q - X + Y \geq D \Rightarrow |P - X| + |Q - Y| \geq D
  • P - Q \leq X - Y - D \Rightarrow P - Q - X + Y \leq -D \Rightarrow |P - X| + |Q - Y| \geq D

Let’s define two sets of points, one is F which is sorted by x + y of points and S which is sorted by x - y of points. Now consider we are at point (X, Y), we can find the points connected to this point at the beginning or at the end of these two sets.

Now start from some point and run BFS, detect its adjacents, add them to queue and erase them from F and S.

This leads to a \mathcal{O}(N \cdot \log N \cdot \log{2 \cdot 10 ^ 9}) solution which is enough for getting 80 points.

Let’s use some trick to make the check function faster. Each time you erase something from front or end of some set, mark that but not erase it from another set. After each step, make sure that there isn’t any marked point at front or end of the set. So the set is not necessary and you can use deque. This leads to \mathcal{O}(N \cdot \log{2 \cdot 10 ^ 9}) solution which is enough for getting full mark.

IMPLEMENTATION -

Author’s code - here.

Second tester’s code - here.

1 Like
2

This can be solved in O(NlogMax) pretty easily

Find 4 corner points (max \pm x \pm y).

Now its enough to consider edges where one of the endpoints is among these 4 points.

7 Likes
3

And it can be extended to multiple dimentions with complexity O(NlogMax2^d) as well by considering 2^d corner points.

4 Likes
4

Nice copy of problem B - Airports , you could at least change the samples

9 Likes
5

Another simple approach, first use 45 degree rotation for every points to make the unreachable region of each point an axis aligned square. Then, while binary searching the answer, to check a distance d is going to make the whole thing connected or not we have to check that if there exists any special point inside the intersection of all the unreachable square region of all special points. Clearly the intersection will be a axis aligned square or rectangle and it can be found in O(N). And the checking if any point is bounded in the intersection also has the same complexity. Overall complexity O(Nlog(2*10^9)).

6

For what value of D we have to check that graph is connected or not. Do we have to apply binary search on D.
Editorial is not clear to me. Please Help.
@abhikalpu Can you please explain this more “Another simple approach, first use 45 degree rotation for every points to make the unreachable region of each point an axis aligned square.”

7

You can also solve this using Manhattan MCST. The smallest edge in your MCST determines the value of D.

Consider rotating the plane by 45 degrees, then collect borders of rectangle containing all points. Find a representative from each border (four total), create edges from the representatives to every other point. Get MCST using Prim’s or Kruskals, then the minimum edge is the answer. Total complexity is O(N log N).

Link to Solution

2 Likes
8

Can you explain it further? :stuck_out_tongue:

9

Hi.

I’m sorry that a similar problem existed on the internet. It was unintentional. Also, I see that in the gym problem, the constraints are not same as that of my problem. In my problem an O(n \log n) solution is required for 100 points, whereas the gym problem can be solved in time complexity O(n \log ^ 2 n). I discussed the problem with the admin and reached the final constraints after some iterations.

10

I believe we can answer the question in O(N) time.
The idea is that if the graph is connected, then every point is connected to at least one of the 4 corner points (the points with maximal \pm x \pm y). First, we connect every point to the farthest corner point in O(N) time. Now, if either every point is connected to one of the +45^\circ corner points, or every point is connected to one of the -45^\circ corner points, then the graph is connected, as the same angle corner points are also connected. Otherwise, if we have used corner points of both angles, then we can connect the two corner points of the same angle without decreasing the minimal distance used. We have yet to connect the two components of the graph. We will find the optimal edge connecting the two subsets between a point of one subset and a corner point of the other subset, hence we can find it in O(N) time.

2 Likes
11

@hikarico Why are you rotating plane by 45 degree ?