PROBLEM LINK:
Author: Ankush Khanna
DIFFICULTY:
Easy-Medium
PREREQUISITES:
PROBLEM:
Given N distinct points on a plane, out of which M points lie on a single straight line (M \leq N). There is only one such line on the plane which can contain more than 2 points. Count the number of distinct straight lines formed after connecting each point with all the other points. Print it modulo 10^9 + 7.
QUICK EXPLANATION:
Combinatorics can help us solve this problem. We can prove that we will have (\binom{N}{2} - \binom{M}{2} + 1) unique lines on this plane after connecting each point with the other one.
EXPLANATION:
Let us first consider all combinations of pairings of the points on this plane, mathematics always has the answer. First of all, there can be \binom{N}{2} ways of choosing two points (for connection) out of the N points on this plane without repetition. Now it is also given that there are M points on a single straight line, therefore, we don’t have to join those points among each other explicitly, because in that case we will be counting more than we need. Also, in that case, we will also count non-unique straight lines.
Therefore, we should consider the ways of connecting two points among those M points and reduce those combinations from our result for all of N points. This way we can eliminate repetition of lines (we need to print minimum possible lines without repetition). Also, if we are counting unique lines, then there is only one way of counting, and there is only one result, so we, in a way, always guarantee to find the minimum number of lines drawn on this 2-D plane (after all connections made).
Number of ways of choosing two points (for connection) out of the M points are \binom{M}{2}. Now, we subtract it from our result for N points and we get \binom{N}{2} - \binom{M}{2}. But, hey, we are forgetting something really important here. We subtracted the result for M points and we just lost all connectivity among those M points. Therefore, we need to add 1 to this result, because there is exactly one way to connect all the M points together (a single straight line).
\therefore we have proved that our answer is going to be (\binom{N}{2} - \binom{M}{2} + 1) mathematically using combinatorics and some geometry about straight lines. Now comes the implementation part.
Sub-Task 1
For the constraints of sub-task 1, we can use a brute force approach by actually counting the ways one by one for each of the points (iterating over all other points). Time complexity will be O(N^2). This way we get 20 points.
Sub-Task 2
Here, we can build a factorial prefix using modular arithmetic, and we can find factorial inverse under modulo of a prime number ( Let K = 10^9 + 7) using Fermat’s Little Theorem. Therefore time and space complexities would be O(N + \log_2 K) and O(N) respectively. This way, we are actually finding the values for the binomial coefficients modulo K. This way we will get 40 points (sub-task 1 and sub-task 2).
\{ O(N) time for building prefix, and O(\log_2 K) time for finding modular inverse using Fermat’s Little Theorem$ }$
Sub-Task 3
By just applying simple mathematics, we can easily figure out that \binom{N}{2} = \frac{N \times (N - 1)}{2}. Therefore we brought down linear time to constant time. \therefore time complexity now is O(1), fair enough to pass the tests.
Note: Apply modular arithmetic very carefully because here we have a subtraction involved. So, take modulo only once and like this:
$(\frac{N \times (N - 1)}{2} - \frac{M \times (M - 1)}{2} + 1) \bmod (10^9 + 7)$COMPLEXITY:
O(1) time per test case, with O(1) auxiliary space used.
SOLUTION:
Setter’s Solution [Plain Text]
Feel free to share your approach. If you have any queries, they are always welcome.