MDIST - Editorial

editorial
, , ,
1

PROBLEM LINK:

Practice
Contest

DIFFICULTY:

EASY

PREREQUISITES:

Segment Tree

PROBLEM:

Given a set of n points, we have to process the following two queries

  • Update i, x, y : Update the ith point to (x,y)
  • Query l, r : Print the maximum Manhattan distance between two points which lie between l to r.

EXPLANATION:

Lets consider a different problem in which we have only one query and no updates. In this problem we have to find two points P1(x1, y1) and P2(x2, y2) such that their Manhattan distance is maximized. Note that the Manhattan distance between any two points can be written as follows

dist(P1, P2) = |x1 - x2| + |y1 - y2|
             = max(  x1 - x2 +  y1 - y2,
                    -x1 + x2 +  y1 - y2,
                     x1 - x2 + -y1 + y2,
                    -x1 + x2 + -y1 + y2) )
             = max(  ( x1 + y1) - ( x2 + y2),
                     (-x1 + y1) - (-x2 + y2),
                     ( x1 - y1) - ( x2 - y2),
                     (-x1 - y1) - (-x2 - y2) )
             = max( f1(P1) - f1(P2), 
                    f2(P1) - f2(P2),
                    f3(P1) - f3(P2),
                    f4(P1) - f4(P2) )
where f1(P) = x+y, f2(P) = -x+y, f3(P) = x-y, f4(P) = -x-y

Note the last expression, not only it is free from any absolute signs but also it follows a pattern which is key to solving this problem. Formally we have to find

\begin{aligned} \max_{(P1,P2)} \{ \text{dist}(P1, P2) \} &= \max_{(P1,P2)} \{ \max(f1(P1) - f1(P2), f2(P1) - f2(P2), f3(P1) - f3(P2), f4(P1) - f4(P2)) \} \\ &= \max (\max_P \{f1(P) \} - \min_P \{f1(P) \}, \max_P \{f2(P) \} - \min_P \{f2(P) \}, \\ & \max_P \{f3(P) \} - \min_P \{f3(P) \}, \max_P \{f4(P) \} - \min_P \{f4(P) \}) \end{aligned}

That is we have to find the point with maximum and minimum f1 value, subtract second from first and do this for f2, f3 and f4 as well and take the maximum among the four.

Now coming back to our original problem, here we have range query and point update, for this we will maintain 4 segment trees each corresponding to f1,f2,f3 and f4 containing the minimum and maximum values of f1,f2,f3 and f4. By this method querying and updating can be done in \mathcal{O}(\log (n)) time.

RELATED PROBLEM:

MOSTDIST
DISTANCE

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here
Tester’s solution can be found here
Editorialist’s solution can be found here

2 Likes
2

HTML, HTML, the link to the solution goes in the href attribute.

https://www.dropbox.com/s/j2if4ntkf8uvm6l/Screenshot%202015-05-31%2014.57.49.png?dl=0

How will we learn if the links to the solutions don’t work? -_-

2 Likes
3

can anyone tell how that max(max(-,-,-,-)) became max(max()-min(),-,-,-)?

4

could you check where it is going wrong?

5

Say f(Point P) = x+y , then max(f(P1) - f(P2)) for all pairs of points is the same as minimising the term to be subtracted i.e f(P2) and maximising term to be added i.e. f(P1). Hence to ensure max value of (f(P1) - f(P2)) we will minimise the term to be subtracted f(P2) and maximise term to be added f(P1) , where P1,P2 belong to set of Points P . Now this process can be done individually for the different functions f1 ,f2 , f3 , f4 resulting in that transformation.

2 Likes