Training Session (Codeforces 1598D)
Tags: Math, geometry

Monocarp is the coach of the Berland State University programming teams. He decided to compose a problemset for a training session for his teams.Monocarp has $$$n$$$ problems that none of his students have seen yet. The $$$i$$$-th problem has a topic $$$a_i$$$ (an integer from $$$1$$$ to $$$n$$$) and a difficulty $$$b_i$$$ (an integer from $$$1$$$ to $$$n$$$). All problems are different, that is, there are no two tasks that have the same topic and difficulty at the same time.Monocarp decided to select exactly $$$3$$$ problems from $$$n$$$ problems for the problemset. The problems should satisfy at least one of two conditions (possibly, both):  the topics of all three selected problems are different;  the difficulties of all three selected problems are different. Your task is to determine the number of ways to select three problems for the problemset.

Input: The first line contains a single integer $$$t$$$ ($$$1 \le t \le 50000$$$) — the number of testcases.The first line of each testcase contains an integer $$$n$$$ ($$$3 \le n \le 2 \cdot 10^5$$$) — the number of problems that Monocarp have.In the $$$i$$$-th of the following $$$n$$$ lines, there are two integers $$$a_i$$$ and $$$b_i$$$ ($$$1 \le a_i, b_i \le n$$$) — the topic and the difficulty of the $$$i$$$-th problem.It is guaranteed that there are no two problems that have the same topic and difficulty at the same time.The sum of $$$n$$$ over all testcases doesn't exceed $$$2 \cdot 10^5$$$.

Output: Print the number of ways to select three training problems that meet either of the requirements described in the statement.

Note: In the first example, you can take the following sets of three problems:  problems $$$1$$$, $$$2$$$, $$$4$$$;  problems $$$1$$$, $$$3$$$, $$$4$$$;  problems $$$2$$$, $$$3$$$, $$$4$$$. Thus, the number of ways is equal to three.

Sample Inputs:
2
4
2 4
3 4
2 1
1 3
5
1 5
2 4
3 3
4 2
5 1

Sample Outputs:
3
10

Solution (Python):
from collections import deque
import heapq
from math import sqrt
import operator
from operator import itemgetter
import sys
import time
import copy
inf_var = 0
if inf_var == 1:
    inf = open('input.txt', 'r')
else:
    inf = sys.stdin
input = inf.readline

def read_one_int():
    return int(input().rstrip('\n'))

def read_one_float():
    return float(input().rstrip('\n'))

def read_list_of_ints():
    res = [int(val) for val in input().rstrip('\n').split()]
    return res

def read_list_of_ints_zero():
    return [int(val) - 1 for val in input().rstrip('\n').split()]

def read_str():
    return input().rstrip()

def calc_c12(stat, n):
    res = 0
    for (_, cnt) in stat.items():
        if cnt >= 2:
            res += cnt * (cnt - 1) // 2 * (n - cnt)
    return res

def calc_c13(stat):
    res = 0
    for (_, cnt) in stat.items():
        if cnt >= 3:
            res += cnt * (cnt - 1) * (cnt - 2) // 6
    return res

def calc_c22(stat_1, stat_2, pairs):
    res = 0
    for (a, b) in pairs:
        if a in stat_1 and b in stat_2:
            cnt_1 = stat_1[a]
            cnt_2 = stat_2[b]
            if cnt_1 >= 2 and cnt_2 >= 2:
                res += (cnt_1 - 1) * (cnt_2 - 1)
    return res

def main():
    tests = read_one_int()
    for _ in range(tests):
        n = read_one_int()
        stat_1 = {}
        stat_2 = {}
        pairs = []
        for _ in range(n):
            (a, b) = read_list_of_ints()
            pairs.append((a, b))
            if a not in stat_1:
                stat_1[a] = 1
            else:
                stat_1[a] += 1
            if b not in stat_2:
                stat_2[b] = 1
            else:
                stat_2[b] += 1
        res = n * (n - 1) * (n - 2) // 6
        res -= calc_c22(stat_1, stat_2, pairs)
        print(res)
if __name__ == '__main__':
    main()

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

def solve():
    n = int(input())
    AB = [list(map(int, input().split())) for _ in range(n)]
    (cntT, cntD) = ({}, {})
    for i in range(n):
        (t, d) = AB[i]
        if t not in cntT:
            cntT[t] = 0
        if d not in cntD:
            cntD[d] = 0
        cntT[t] += 1
        cntD[d] += 1
    ans = n * (n - 1) * (n - 2) // 6
    for i in range(n):
        (t, d) = AB[i]
        ans -= (cntT[t] - 1) * (cntD[d] - 1)
    return ans
for _ in range(int(input())):
    print(solve())

Solution (Python):
from collections import defaultdict
from sys import stdin, stdout
for _ in range(int(stdin.readline())):
    n = int(stdin.readline())
    (da, db) = (defaultdict(int), defaultdict(int))
    arr = []
    for _ in range(n):
        (a, b) = map(int, stdin.readline().split())
        da[a] += 1
        db[b] += 1
        arr.append([a, b])
    ans = 0
    for (a, b) in arr:
        ans += (da[a] - 1) * (db[b] - 1)
    stdout.write(str(n * (n - 1) * (n - 2) // 6 - ans) + '\n')