Problem Link: contest, practice
Difficulty: Easy
Pre-requisites: Binary heap, Geometry, Manhattan distance
Problem:
Let’s consider a set of points S. Your task is to implement a data structure that can process the following queries efficiently:
- “+ X Y” - add a new point P with coordinates (X, Y) to S;
- “- N” - remove the point that was added during the N’th adding query from S;
- “? X Y” - calculate the maximal Manhattan distance between a point P with coordinates (X, Y) and any point from S.
It’s required to implement an on-line solution, i.e. which processes queries in the order of their appearance.
Explanation:
Let’s transform the formula of Manhattan distance a little bit:
dist(P1, P2) = |X1 - X2| + |Y1 - Y2| = max(X1 - X2, X2 - X1) + max(Y1 - Y2, Y2 - Y1) = max((X1 + Y1) - (X2 + Y2), (X1 - Y1) - (X2 - Y2), (-X1 + Y1) - (-X2 + Y2), (-X1 - Y1) - (-X2 - Y2)) = max(f_{1}(P1) - f_{1}(P2), f_{2}(P1) - f_{2}(P2), f_{3}(P1) - f_{3}(P2), f_{4}(P1) - f_{4}(P2)), where
- f_{1}(P) = X + Y;
- f_{2}(P) = X - Y;
- f_{3}(P) = -X + Y;
- f_{4}(P) = -X - Y.
In other words, dist(P1, P2) equals to the maximum of four values, that don’t contain abs() function anymore.
It’s time to make the key observation of this problem:
Let’s suppose that we are to find the maximal Manhattan distance between a point P and any point from S. The key fact is that there are only four candidates to be the most distant one: the ones with the maximal f_{1}(P), f_{2}(P), f_{3}(P) and f_{4}(P) from S.
So, we can maintain S as four separate binary heaps H_{1}, H_{2}, H_{3} and H_{4}, each point of S belongs to each of H_{i}. The points are ordered according to f_{i}(P) in heap H_{i}.
Now, if we want to add a new point to S, then we add it to each of H_{i}. If we want to calculate the maximal Manhattan distance between a point P and any point from S, then we find the most distant point from S(as the most distant one among ones with the maximal f_{1}(P), f_{2}(P), f_{3}(P) and f_{4}(P)).
What about removing points from S? As we know, a binary heap doesn’t provide any kind of removing except removing from the top of the heap. But that’s OK, we won’t remove them for real until they affect the answers. We can just mark removed points somehow and every time, when a ‘removed’ point is on the top of one of the binary heaps, we remove it from this heap for real. The reason why we are not removing a point from S until it is not on the top is that such a point doesn’t affect the answers, since only the ones on the tops are considered as candidite for being the most distant point every time we are interested to know that information.
The total complexity of the solution is O(Q log Q).
Please, check out Setter’s and Tester’s solutions for your better understanding.
Setter’s Solution: link
Tester’s Solution: link