You are not logged in. Please login at www.codechef.com to post your questions!

×

TRAVELAL - Editorial

1
3

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.

This question is marked "community wiki".

asked 30 Jul '17, 00:19

arpa's gravatar image

6★arpa
4927
accept rate: 0%

edited 31 Jul '17, 21:34


link

answered 30 Jul '17, 01:39

fmota's gravatar image

7★fmota
911
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★

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.

link

answered 30 Jul '17, 01:28

rajat1603's gravatar image

7★rajat1603
1.0k112
accept rate: 4%

Can you explain it further? :p

(30 Jul '17, 12:28) vijju123 ♦4★

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

link

answered 30 Jul '17, 01:30

rajat1603's gravatar image

7★rajat1603
1.0k112
accept rate: 4%

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

link

answered 30 Jul '17, 12:15

hikarico's gravatar image

5★hikarico
1.8k1515
accept rate: 28%

edited 30 Jul '17, 12:19

@hikarico Why are you rotating plane by 45 degree ?

(02 Aug '17, 14:22) rishus233★

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.

link

answered 30 Jul '17, 17:43

h_bar's gravatar image

4★h_bar
422
accept rate: 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))$.

link

answered 30 Jul '17, 05:12

abhikalpu_123's gravatar image

4★abhikalpu_123
1475
accept rate: 8%

edited 30 Jul '17, 05:18

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

link

answered 30 Jul '17, 11:28

vishesh_345's gravatar image

1★vishesh_345
2567
accept rate: 8%

edited 30 Jul '17, 11:32

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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:

×14,435
×821
×107
×7

question asked: 30 Jul '17, 00:19

question was seen: 1,181 times

last updated: 02 Aug '17, 15:19