We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Having solved this with a “wrong” algorithm, I went through the editorial and re-created author’s solution, which is more robust and elegant than mine.
Here’s the “correct” way to think about this problem:
(Duplet = two points; pair = two duplets.)
An answer is correct iff it is the maximum pair distance among all possible pairings of given set of duplets. An answer is valid iff there is a pair with distance of at least that answer.
Correct answer lies between [0, c]. Answer 0 is valid for any set of at least two duplets. Answer c is never valid (in fact, correct answer can never grow greater than c/4).
If correct answer is R, then all answers in [0, R] are valid, and all answers in [R + 1, c] are invalid.
With problem presented as such, it’s easy to see, that the answer is best found using binary search. We start with left pivot being 0, and right pivot being c, and maintain an invariant: left must remain valid, right must remain invalid. In the end, when two pivots are right next to each other, left pivot is the maximum valid answer, which makes it the correct answer.
It’s easier to check an answer for validity, than it is to check it for correctness. If candidate is r, then for each duplet we look for any other duplet with points removed by at least r. Author uses segment tree and range maximum query (RMQ) to check validity.
Binary search is O(log c), iterating through every duplet is O(n), and and searching for complimentary duplet with RMQ is O(log n). So this solution is O(n * log n * log c) which is better than quadratic.
I will post my Kotlin port of author’s solution in reply to this post.
Distant Pairs
You are viewing a single comment's thread. Return to all comments →
Having solved this with a “wrong” algorithm, I went through the editorial and re-created author’s solution, which is more robust and elegant than mine.
Here’s the “correct” way to think about this problem:
(Duplet = two points; pair = two duplets.)
An answer is correct iff it is the maximum pair distance among all possible pairings of given set of duplets. An answer is valid iff there is a pair with distance of at least that answer.
Correct answer lies between
[0, c]
. Answer0
is valid for any set of at least two duplets. Answerc
is never valid (in fact, correct answer can never grow greater thanc/4
).If correct answer is
R
, then all answers in[0, R]
are valid, and all answers in[R + 1, c]
are invalid.With problem presented as such, it’s easy to see, that the answer is best found using binary search. We start with
left
pivot being0
, andright
pivot beingc
, and maintain an invariant:left
must remain valid,right
must remain invalid. In the end, when two pivots are right next to each other,left
pivot is the maximum valid answer, which makes it the correct answer.It’s easier to check an answer for validity, than it is to check it for correctness. If candidate is
r
, then for each duplet we look for any other duplet with points removed by at leastr
. Author uses segment tree and range maximum query (RMQ) to check validity.Binary search is
O(log c)
, iterating through every duplet isO(n)
, and and searching for complimentary duplet with RMQ isO(log n)
. So this solution isO(n * log n * log c)
which is better than quadratic.I will post my Kotlin port of author’s solution in reply to this post.