Forming Triangles (Codeforces 1922B)
Tags: Math, combinatorics

You have $$$n$$$ sticks, numbered from $$$1$$$ to $$$n$$$. The length of the $$$i$$$-th stick is $$$2^{a_i}$$$.You want to choose exactly $$$3$$$ sticks out of the given $$$n$$$ sticks, and form a non-degenerate triangle out of them, using the sticks as the sides of the triangle. A triangle is called non-degenerate if its area is strictly greater than $$$0$$$.You have to calculate the number of ways to choose exactly $$$3$$$ sticks so that a triangle can be formed out of them. Note that the order of choosing sticks does not matter (for example, choosing the $$$1$$$-st, $$$2$$$-nd and $$$4$$$-th stick is the same as choosing the $$$2$$$-nd, $$$4$$$-th and $$$1$$$-st stick). 

Input: The first line contains one integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.Each test case consists of two lines:  the first line contains one integer $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$);  the second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le n$$$). Additional constraint on the input: the sum of $$$n$$$ over all test cases does not exceed $$$3 \cdot 10^5$$$.

Output: For each test case, print one integer — the number of ways to choose exactly $$$3$$$ sticks so that a triangle can be formed out of them.

Note: In the first test case of the example, any three sticks out of the given $$$7$$$ can be chosen.In the second test case of the example, you can choose the $$$1$$$-st, $$$2$$$-nd and $$$4$$$-th stick, or the $$$1$$$-st, $$$3$$$-rd and $$$4$$$-th stick.In the third test case of the example, you cannot form a triangle out of the given sticks with lengths $$$2$$$, $$$4$$$ and $$$8$$$.

Sample Inputs:
4
7
1 1 1 1 1 1 1
4
3 2 1 3
3
1 2 3
1
1

Sample Outputs:
35
2
0
0

Solution (Python):
from sys import stdin

def input():
    return stdin.readline()[:-1]
from collections import defaultdict

def eureka():
    n = int(input())
    arr = list(map(int, input().split()))
    l = [0] * (n + 1)
    for i in arr:
        l[i] += 1
    total = 0
    count = 0
    for i in range(n + 1):
        a = l[i]
        if a == 2:
            count += total
        elif a > 2:
            count += a * (a - 1) // 2 * total + a * (a - 1) * (a - 2) // 6
        total += a
    print(count)
for _ in range(int(input())):
    eureka()

Solution (Python):
import sys
input = sys.stdin.readline

def ii():
    return int(input())

def i():
    return input()

def ls():
    return [x for x in input().split()]

def ils():
    return [int(x) for x in input().split()]

def tup():
    return map(int, input().split())

def sils():
    return sorted([int(x) for x in input().split()])

def solve():
    n = ii()
    a = ils()
    b = [0] * (n + 1)
    for i in a:
        b[i] += 1
    c = 0
    sum = 0
    for i in range(n + 1):
        if b[i] == 2:
            c += sum
        elif b[i] > 2:
            c += b[i] * (b[i] - 1) // 2 * sum + b[i] * (b[i] - 1) * (b[i] - 2) // 6
        sum += b[i]
    print(c)
    return
for __ in range(ii()):
    solve()

Solution (Python):
def calculate_factorial3(num):
    return num * (num - 1) * (num - 2) // 6

def calculate_factorial2(num):
    return num * (num - 1) // 2

def process_test_case():
    num = int(input())
    occurrences = [0] * (num + 1)
    for element in map(int, input().split()):
        occurrences[element] += 1
    result = 0
    previous = 0
    for count in occurrences:
        if count >= 3:
            result += calculate_factorial3(count)
        if count >= 2:
            result += calculate_factorial2(count) * previous
        previous += count
    print(result)
if __name__ == '__main__':
    test_cases = int(input())
    for _ in range(test_cases):
        process_test_case()