PROBLEM LINK:
Author: Bhushan Khanale
Editorialist: Bhushan Khanale
DIFFICULTY:
EASY
PREREQUISITES:
None
PROBLEM:
There are N total points. Task was to select three points out of those such that the distance between any two points should not exceed K. The problem was to find the total number of such pairs that can be selected as per the task.
QUICK EXPLANATION:
The distance between any points should not exceed K. Hence we need to select all the pairs of points that lie within a range of [x, x+K].
EXPLANATION:
In order to find out all the pairs lest first select the rightmost point out of our three points. We can simply iterate over all the points in ascending order of their X-coordinate. At the same time we will maintain a pointer to the leftmost point which lays on the distance not greater than K from the current rightmost point. We can easily find out the number of points in the segment between two pointers, excluding the rightmost point. Lets call this number d. Then there exists exactly d*(d-1)/2 pairs of points with the fixed rightmost point. Then we can sum up these values for all rightmost points.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.