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

×

# TDRIVER - Editorial

Author: Konstantsin Sokol
Tester: Gedi Zheng
Editorialist: Miguel Oliveira

Medium.

# PREREQUISITES:

Geometry, Manhattan distance.

# PROBLEM

Given a set of N points and constants a and b, calculate the sum of the distances between each pair of points. However, the distance between 2 points is defined as max(a × |x1 - x2|, b × |y1 - y2|).

# QUICK EXPLANATION

• Transform each coordinate (x, y) into ($\frac{a * x + b * y}{2}$, $\frac{a * x - b * y}{2}$).
• Calculate the distance between all pairs of points using the Manhattan distance on the new coordinates.

# EXPLANATION

Problem MOSTDIST, required a transformation from Manhattan distance metric to maximum metric (editorial here). Here, we do the reverse. Suppose $a = b = 1$. Then the distance between points A and P is $max(|A_x - P_x| , |A_y - P_y|)$.

$max(|A_x - P_x| , |A_y - P_y|) = max(A_x - P_x , P_x - A_x , A_y - P_y , P_y - A_y)$

Let's perform the following variable transformation

$\begin{cases} A_x = S_x + S_y \\ A_y = S_x - S_y \\ P_x = T_x + T_y \\ P_y = T_x - T_y \end{cases}$

We get

$max( Ax - Px , Px - Ax , Ay - Py , Py - Ay ) =$

$max( (Sx+Sy) - (Tx+Ty), (Tx+Ty) - (Sx+Sy), (Sx-Sy) - (Tx-Ty), (Tx-Ty) - (Sx-Sy) )$

Rearrange this into

$max( (Sx-Tx) + (Sy-Ty), (Tx-Sx) + (Ty-Sy), (Sx-Tx) + (Sy-Ty), (Tx-Sx) + (Ty-Sy) ) =$

$max( Sx - Tx , Tx - Sx ) + max( Sy - Ty , Ty - Sy ) =$

$|Sx-Tx| + |Sy-Ty|$

So we were able to get rid of the maximum function and only have a manhattan distance on these 4 variables. Inverting the transformation, we have

$\begin{cases} S_x = \frac{A_x + A_y}{2} \\ S_y = \frac{A_x - A_y}{2} \\ T_x = \frac{P_x + P_y}{2} \\ T_y = \frac{P_x - P_y}{2} \end{cases}$

Hence, we can modify the given point coordinates using this transformation and then calculate the manhattan distance between all the points using the new coordinate system.

In order to take the parameters a and b into account, we can just multiply each variable in x by a and each variable in y by b.

Note that we can avoid using floating point numbers in the coordinates due to division by 2 by using the transformations $new_x = x + y, new_y = x - y$ and divide the result by 2 in the end.

Time Complexity

We sort the coordinates and then process them in linear time. Hence, the total time complexity is O(N log N).

# AUTHOR'S AND TESTER'S SOLUTIONS:

This question is marked "community wiki".

asked 19 Apr '15, 22:42

5★mogers
659716
accept rate: 25%

why do we transform the co-ordinates exactly in that fashion ?

(20 Apr '15, 13:19)

I have gone through MOSTDIST editorial and I understood it.

But I can't figure out how logic of MOSTDIST is applied here. Why you are converting coords from (x,y) to ((ax+by)/2,(ax-by)/2)

How sorting xx and yy coords and calculating the manhattan distance separately conserving equation of distance between two points : max(a|x1-x2|,b|y1-y2|) ?

(20 Apr '15, 19:10)
1

I added an explanation, please take a look.

(20 Apr '15, 23:10) 5★

 2 Let's say the proof of the transformation again. $d_{1,2}^M = |x_1^M-x_2^M| +|y_1^M-y_2^M|=| \frac{a \times x_1^C+b \times y_1^C - a \times x_2^C -b \times y_2^C}{2}| +| \frac{a \times x_1^C -b \times y_1^C - a \times x_2^C +b \times y_2^C}{2}|$ $= | \frac{a \times (x_1^C -x_2^C) +b \times (y_1^C - y_2^C)}{2} +| \frac{a \times (x_1^C -x_2^C) -b \times (y_1^C - y_2^C)}{2}|$ $=|q+r|+|q-r|$ where $q=\frac{a \times (x_1^C -x_2^C)}{2}$ and $r=\frac{b \times (y_1^C -y_2^C)}{2}$ for any q and r we can prove $|q+r|+|q-r|= max(q+r, -q-r) +max(q-r, -q+r)$ $= max(q+r+q-r, q+r-q+r, -q-r+q-r, -q-r-q+r)$ $= max(2 \times q , 2 \times r, -2 \times r, -2 \times q)$ $= max( 2 \times max(q, -q), 2 \times max(r,-r))=2 \times max(|q|, |r|)$ So applying this in the above equation: $d_{1,2}^M= max(a \times |x_1^C -x_2^C|, b \times |y_1^C - y_2^C|)= d_{1,2}^C$ Q.E.D. answered 21 Apr '15, 02:31 0★annaqeeb 41●3 accept rate: 0%
 1 This answer is based on the above tutorial and the Setter Solution The names of distances are based on user Khaled Kee and Wikipedia. For any Type of distances, the summantion of inner distance D for N nodes can be calculated by any one of the following formulas: $D_N =\frac{1}{2} \sum_{i=1}^{N} \sum_{j=1}^{N} d_{i,j}$ $= \sum_{i=2}^N \sum_{j=1}^{i-1} d_{i,j}$ $=\sum_{i=1}^N \sum_{j=1}^{i-1} d_{i,j}$ These formulas are simple, $d_i,j$ is distance between Point i and j. If you calculate for all possible values of i and j then you calculated the distance twice. If you choose that j smaller than i, then it is calculated once. Direct application of any of these formulas is $O(n^2)$. The last formula is interesting as it can be turned to a recursive formula: $D_i = D_{i-1}+ \sum_{j=1}^{i-1} d_{i,j}$ We will get back to this formula later in this answer so keep it in mind. Before Going further while the previous rule apply to any type of distance, what was meant with type of distance? Here are 3 known types of distances: -Euclidean distance : this is the distance between two points, if you have infinite number of directions to move in as in Geometry in mid and High school $d_{i,j}= \sqrt {{x_i -x_j}^2 +{y_i-y_j}^2}$ -Manhattan distance : this is the distance between two points, if you have 4 directions to move, for example: rooks and bishops in chessboard. Also called City block distance or Taxicab distance. $d_{i,j}= |{x_i-x_j}| +|{y_i-y_j}|$ -Chebyshev distance : this is the distance between two points, if you have 8 directions to move, for example: king in chessboard. Also called Maximum metric or Chessboard distance. $d_{i,j}= max(|{x_i-x_j}| ,|{y_i-y_j}|)$ The problem is about calculating total inner Chebyshev distance. Note that Chebychev distance in this problem is scaled by factors (a,b) for the (x,y) coordinates. Now we need to reduce the time Complexity from $O(n^2)$ to $O(n log(n))$, how? First we will transform the coordinates given in the problem , so that the inner Chebyshev distance in the given coordinated $(x_C, y_C)$ is equal to the inner Manhattan distance int the transformed coordinates $(x_M,y_M)$. The transformation is: $(x_M,y_M)= (\frac{a \times x_C+ b \times y_C}{2}, \frac{a \times x_C+ b \times y_C}{2})$ Why is Manhattan distance for points $P_M = (x_M,y_M)= (\frac{a \times x_C+ b \times y_C}{2}, \frac{a \times x_C+ b \times y_C}{2})$ is equal to Chebyshev distance for points $P_C =(x_C,y_C)$ this is already mentioned at Problem MOSTDIST - Editorial. I added another answer to the current question that reviews the proof. Now back to our main problem, how could this improve complexity? Summation of Manhattan distance have a very nice properties. First they are separable for each coordinate. $D_i = D_{i-1}+ \sum_{j=1}^{i-1} d_{i,j}$ $= D_{i-1}+ \sum_{j=1}^{i-1}(|{x_i-x_j}| +|{y_i-y_j}|)$ $=D_{i-1}^x+ \sum_{j=1}^{i-1} |x_i-x_j| + D_{i-1}^y+\sum_{j=1}^{i-1} |y_i-y_j|$ $=D_i^x +D_i^y$ What if the values are sorted, i.e, if i is larger than j then $x_i \geq x_j$ ,then we can safely remove the absolute value function,as the value is always zero or positive , so: $D_i^x= D_{i-1}^x+ \sum_{j=1}^{i-1}(x_i-x_j)= D_{i-1}^x +(i-1) \times x_i - \sum_{j=1}^{i-1}x_j$ $D_i^y= D_{i-1}^y+ \sum_{j=1}^{i-1}(y_i-y_j)= D_{i-1}^y +(i-1) \times y_i - \sum_{j=1}^{i-1}y_j$ The first calculation requires sorting according to x, the second according to y. this is not a problem as they do not depend on each other at all. last note , do not divide by 2 while transforming as this will cause errors in the integer odd values. instead calculate the whole sum then divide it by 2, in the end. If you have any problems , see my submission . The last summation can be calculated easily from its previous value. Now the complexity is max( O(sorting), O(summation) )=max( O(n log(n)), O(n))= O(n log(n)) answered 21 Apr '15, 02:28 0★annaqeeb 41●3 accept rate: 0%
 0 Nice Solution...!! answered 20 Apr '15, 11:48 100●9 accept rate: 5%
 0 can anyone explain the logic behind the question. answered 20 Apr '15, 16:32 198●1●5 accept rate: 0% 1 I elaborated the coordinate transformation, please take a look. (20 Apr '15, 23:11) mogers5★
 toggle preview community wiki:
Preview

### Follow this question

By Email:

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

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,852
×1,301
×647
×62
×31
×19

question asked: 19 Apr '15, 22:42

question was seen: 2,885 times

last updated: 21 Apr '15, 05:43