CLOSESTQ - Editorial

closestq
divide-and-conquer
ltime47
medium-hard
sets
sqrt

#1

Practice
Contest

Author: Ildar Gainullin
Tester: Lewin Gan
Editorialist: Misha Chorniy

Difficulty:

Medium-Hard

Pre-Requisites:

Set

Problem Statement

There is a set of points in 2D, we need to process next queries. Add/erase point in the set of points, and output the square of distance between pair of nearest points. If size of set less than 2, output 0. Initially the set is empty, coordinates of points lies in a range from 1 to 500.

Subtasks 1 and 2

Number of queries is less than 2500, we can store all paires squares of distances in set. Adding/erasing point into the set equivalent adding/erasing squares of distance to all points which lies in the set. After that we need to print minimal element in the set. Complexity will be $O(Q^2 log Q)$

points = [] dist = {} for i=1..Q c,x,y=read() if c == '+': for i in points: dist.insert(square(points*, (x,y))) points.add((x,y)) else: points.erase((x,y)) for i in points: dist.erase(square(points*, (x,y))) if !dist.empty(): print dist.minElement() else: print 0

Subtask 3

We can use divide-and-conquer by queries to solve this problem, consider problem only with adding queries. Suppose that we are adding point $(x, y)$ into set and $ans$ is the current minimal square of distance between two points in the set, if set contains less than 2 points, assume $ans = 10^9$. We need to check only those points $(dx, dy)$, which makes new answer less than $ans$. Let's maintain for each $x$ the set of $y$ - coordinates of points which has the same $x$. If we need to update answer for a point $(x, y)$, let's iterate over $dx$, and check two points(if they exists), point $(dx, dy1)$, where $dy1 >= y$ and $(dx, dy2)$, where $dy2 < y$ we can find them in $O(log 500)$ and update the answer. We don't see, if $(dx -x)^2>ans$, because it has no sense to update the answer. When a number of points in the set are more then a couple of thousands, $ans$ won't be big. How to process erase queries? At first, we will solve this problem in offline, i.e initially read all queries and after that process it. At second, for each time of adding a point, let's find nearest time of erasing this point, if this point will be in the set to the end, assume that we erase it in moment of time $Q+1$, after that each point has an interval [L; R], where it is alive(i.e contains in the set). One point can have several intervals. $intervals$ contains all intervals for points. Look at the following code:

solve(L, R, intervals, ans = 1e9) { int M = (L + R) / 2 newIntervals = [] for cint in intervals if cint.end < L OR cint.begin > R //Point which is added in moment of time cint.begin won't be used in queries in a range from L..R, because it erased in the moment of time cint.end continue if cint.begin <= L AND cint.end > R //Point will be used for any query in a range L..R, we add it AddPoint(x[cint.begin], y[cint.begin], newAns) //adding point and recalcuating ans else: //Otherwise we will process this point somewhere deeper, number of such adding is O(R - L) in array newIntervals newIntervals.add(cint) if (L != R) { solve(L, M, newIntervals, newAns) solve(M + 1, R, newIntervals, newAns) } else res[L] = newAns rollback() //rollback all changes which were done in this call of function with AddPoint } solve(1, Q, 1e9)

Total complexity of this algorithm is $O(Q * log Q * 500 * log 500)$ but with very small constant.

Solution:

Setter's solution can be found here
Tester's solution can be found here

Please feel free to post comments if anything is not clear to you.


#2

Please tag ltime47 and editorial so that this post is visible from the link given on the contest page.