DOTSTOLI - Editorial

editorial
1

PROBLEM LINK:

Practice
Contest

Author: Yash Shah
Tester: Roshan Gupta, Shivam Sarang, Hrishikesh Patel
Editorialist: Yash Shah

DIFFICULTY:

EASY

PROBLEM:

Chef is given N dots out of which M dots are co-linear. Co-Linear
dots means all dots lie in same straight line.

Can you help chef to find maximum number of lines he can make
with N dots ? If M > N output should be 0.

Note: Usage of any inbuilt library should be avoided.

EXPLANATION:

Sample Test Case:

Input:
1
4 3

Output:
4

  • When there are 4 points with 3 collinear points we can form
    maximum of 4 lines.

SOLUTIONS:

Setter's Solution 
import sys


def nCk(n, k):
    C = [0] * (k + 1)
    C[0] = 1
    for i in range(1, n + 1):
        j = min(i, k)
        while j > 0:
            C[j] = C[j] + C[j - 1]
            j = j - 1
        return C[k]


def count_Straightlines(n, m):
    return nCk(n, 2) - nCk(m, 2) + 1


t = int(input())
while t:
    n, m = map(int, sys.stdin.readline().split())
    res = count_Straightlines(n, m)
    if res < 0:
        print("0")
    else:
        print(res)
    t -= 1