×

# TRAVELAL - Editorial

 1 3 PROBLEM LINK - 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. This question is marked "community wiki". asked 30 Jul '17, 00:19 6★arpa 49●2●7 accept rate: 0%

 9 http://codeforces.com/gym/100959/attachments/download/4248/20152016-petrozavodsk-winter-training-camp-makoto-rng58-soejima-sontest-4-en.pdf Nice copy of problem B - Airports , you could at least change the samples answered 30 Jul '17, 01:39 7★fmota 91●2 accept rate: 0% 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. (30 Jul '17, 16:37) arpa6★
 7 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. answered 30 Jul '17, 01:28 1.0k●1●12 accept rate: 4% Can you explain it further? :p (30 Jul '17, 12:28)
 4 And it can be extended to multiple dimentions with complexity $O(NlogMax2^d)$ as well by considering $2^d$ corner points. answered 30 Jul '17, 01:30 1.0k●1●12 accept rate: 4%
 2 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 answered 30 Jul '17, 12:15 4★hikarico 1.8k●1●5●15 accept rate: 28% @hikarico Why are you rotating plane by 45 degree ? (02 Aug '17, 14:22) rishus233★
 2 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. answered 30 Jul '17, 17:43 4★h_bar 42●2 accept rate: 0%
 0 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))$. answered 30 Jul '17, 05:12 147●5 accept rate: 8%
 0 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." answered 30 Jul '17, 11:28 256●7 accept rate: 8%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,026
×962
×108
×7

question asked: 30 Jul '17, 00:19

question was seen: 1,243 times

last updated: 02 Aug '17, 15:19