PROBLEM LINK:
Author: Anurag Anand
Tester: Vaibhav Gosain
DIFFICULTY:
Easy-Medium
PREREQUISITES:
Probabilities
PROBLEM:
Given N points on a 2D plane, check whether there is a line containing at least p percent of the points.
EXPLANATION:
A naive algorithm is to pick a point and assuming it as origin find the count of slopes of other points and check if any slope has sufficient number of points. However, the time complexity of this algorithm is O(N^2\log(N)). We claim that we do not need to check with all the points as origin.
Let us suppose there is a line L with at least p\% of the points. If we choose a random point as origin, the probability that it does not lie on L less than or equal to (1-p). We repeat this process m times i.e. Each time we choose a random point as origin and find the count of slopes of other points. The probability that none of the points on L we chosen as origin is less than or equal to (1-p)^m. Hence, the probability that we would have chosen at least one point on L is \ge 1 - (1-p)^m. The worst case is when p=1. If we choose m=500, the probability of success is 1-0.99^{500} \approx 0.9934. If we do not find any such line till m iterations, we say that there is no such line with very high probability.
AUTHOR’S SOLUTION:
Author’s solution can be found here.