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.
I managed to beat all test cases, but just barely. (It’s so close, that when I keep submitting my accepted solution, sometimes it passes, and sometimes it doesn’t, with one or two cases timing out.)
Here’s the problem reworded:
We are given a circle and n duplets of points (a, b) distributed along circle’s circumference c.
Every duplet contains two points that divide circumference into exactly two segments. (A segment could be zero-length.)
The shortest of those two segments is said to be the duplet’s distance (duplet.dist).
Every pair of such duplets contains four points that divide circumference into exactly four segments. (A segment could be zero-length.)
The shortest of those four segments is said to be the distance between duplets (pair(duplet1, duplet2).dist).
The question is: for every possible pairings of given duplets, what is the largest possible pair distance?
Here’s my approach to the solution:
For any four points whatsoever, the shortest segment can only get as large as c/4. (If a segment gets bigger than that, it is guaranteed to no longer be the shortest one.) This means, that our answer is always within [0, c/4].
Given a single duplet of points, we can calculate duplet.bestHope — the largest pair distance we can possibly achieve with this duplet. Here’s how you calculate it (go at it on a whiteboard if you don’t trust me):
So, if we know bestHope for every duplet, we can sort them in order of decreasing bestHope, and then go at them the hard way (O(n*n)). We pair each next duplet with every duplet seen so far, while keeping global record of currentMaximum distance. As soon as currentMaximum exceeds the next duplet’s bestHope, we bail from the loop and return currentMaximum.
This can be refined a bit: each current duplet need only be paired against those duplets that have both their points removed at least by currentMaximum from both points of current duplet.
Solution above works, but takes way too long if duplets are highly localized. E.g., if all a points of all duplets are concentrated within a narrow segment of circumference, the answer can’t get larger than that segment’s width.
For those cases I elected a different approach:
Find the segment where points are concentrated. This is boring and not elegant, but doable.
Then we again start going through all of the pairs, but this time we start picking them at both edges of the concentration segment, going inward.
As soon as currentMaximum grows to the width of the concentration segment (latter gets smaller as we chip away at the edges), we bail from the loop and return currentMaximum.
I will post the entire solution, written in Kotlin, as a reply to this post. I invite everyone to offer improvements, or maybe suggest a completely different approach.
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Distant Pairs
You are viewing a single comment's thread. Return to all comments →
I managed to beat all test cases, but just barely. (It’s so close, that when I keep submitting my accepted solution, sometimes it passes, and sometimes it doesn’t, with one or two cases timing out.)
Here’s the problem reworded:
n
duplets of points(a, b)
distributed along circle’s circumferencec
.duplet.dist
).pair(duplet1, duplet2).dist
).Here’s my approach to the solution:
c/4
. (If a segment gets bigger than that, it is guaranteed to no longer be the shortest one.) This means, that our answer is always within[0, c/4]
.Given a single duplet of points, we can calculate
duplet.bestHope
— the largest pair distance we can possibly achieve with this duplet. Here’s how you calculate it (go at it on a whiteboard if you don’t trust me):So, if we know
bestHope
for every duplet, we can sort them in order of decreasingbestHope
, and then go at them the hard way (O(n*n)
). We pair each next duplet with every duplet seen so far, while keeping global record ofcurrentMaximum
distance. As soon ascurrentMaximum
exceeds the next duplet’sbestHope
, we bail from the loop and returncurrentMaximum
.currentMaximum
from both points of current duplet.Solution above works, but takes way too long if duplets are highly localized. E.g., if all
a
points of all duplets are concentrated within a narrow segment of circumference, the answer can’t get larger than that segment’s width.For those cases I elected a different approach:
currentMaximum
grows to the width of the concentration segment (latter gets smaller as we chip away at the edges), we bail from the loop and returncurrentMaximum
.I will post the entire solution, written in Kotlin, as a reply to this post. I invite everyone to offer improvements, or maybe suggest a completely different approach.