Playing in a Casino (Codeforces 1808B)
Tags: Math, sortings

  Galaxy Luck, a well-known casino in the entire solar system, introduces a new card game.In this game, there is a deck that consists of $$$n$$$ cards. Each card has $$$m$$$ numbers written on it. Each of the $$$n$$$ players receives exactly one card from the deck.Then all players play with each other in pairs, and each pair of players plays exactly once. Thus, if there are, for example, four players in total, then six games are played: the first against the second, the first against the third, the first against the fourth, the second against the third, the second against the fourth and the third against the fourth.Each of these games determines the winner in some way, but the rules are quite complicated, so we will not describe them here. All that matters is how many chips are paid out to the winner. Let the first player's card have the numbers $$$a_1, a_2, \dots, a_m$$$, and the second player's card — $$$b_1, b_2, \dots, b_m$$$. Then the winner of the game gets $$$|a_1 - b_1| + |a_2 - b_2| + \dots + |a_m - b_m|$$$ chips from the total pot, where $$$|x|$$$ denotes the absolute value of $$$x$$$.To determine the size of the total pot, it is necessary to calculate the winners' total winnings for all games. Since there can be many cards in a deck and many players, you have been assigned to write a program that does all the necessary calculations.

Input: Each test consists of several test cases. The first line contains one integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases. The description of the test cases follows.The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \cdot m \le 3\cdot 10^5$$$) — the number of cards in the deck and the count of numbers on the one card.Each of the following $$$n$$$ lines of the test case set contains $$$m$$$ integers $$$c_{i,j}$$$ ($$$1 \le c_{i,j} \le 10^6$$$) — a description of the $$$i$$$-th card.It is guaranteed that the total $$$n \cdot m$$$ in all tests does not exceed $$$3 \cdot 10^5$$$.

Output: For each test case, print one number — the total amount of winnings from all games.

Note: Consider the first test case.In the game between the first and second player, the winner receives $$$|1-7| + |4-9| + |2-2| + |8-1| + |5-4| = 19$$$ chips.In the game between the first and third player, the winner receives $$$|1-3| + |4-8| + |2-5| + |8-3| + |5-1| = 18$$$ in chips.In the game between the second and third player, the winner receives $$$|7-3| + |9-8| + |2-5| + |1-3| + |4-1| = 13$$$ chips.The total is $$$19 + 18 + 13 = 50$$$ chips.

Sample Inputs:
3
3 5
1 4 2 8 5
7 9 2 1 4
3 8 5 3 1
1 4
4 15 1 10
4 3
1 2 3
3 2 1
1 2 1
4 2 7

Sample Outputs:
50
0
31

Solution (Python):
import sys
import copy
import heapq
import bisect
import functools
from math import *
from collections import defaultdict
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import groupby
from itertools import accumulate
readline = sys.stdin.readline

def solve():
    (n, m) = map(int, readline().split())
    a = [[] for _ in range(m)]
    for i in range(n):
        t = list(map(int, readline().split()))
        for i in range(len(t)):
            a[i].append(t[i])
    ans = 0
    for i in range(m):
        a[i].sort()
        for j in range(1, n):
            ans += j * (n - j) * (a[i][j] - a[i][j - 1])
    print(ans)

def main():
    t = 1
    t = int(input())
    for i in range(t):
        solve()
if __name__ == '__main__':
    main()

Solution (Python):
import sys
from collections import deque
from math import gcd
from collections import Counter

def find_gcd(numbers):
    result = numbers[0]
    for number in numbers[1:]:
        result = gcd(result, number)
    return result
input = sys.stdin.readline

def readList():
    return list(map(int, input().split()))

def readInt():
    return int(input())

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

def readStr():
    return input().strip()

def solve():
    (n, m) = readInts()
    matrix = [[] for _ in range(m)]
    ans = 0
    for _ in range(n):
        tmp = readList()
        for idx in range(len(tmp)):
            matrix[idx].append(tmp[idx])
    for col in matrix:
        tmp = sorted(col)
        for j in range(1, n):
            ans += j * (n - j) * (tmp[j] - tmp[j - 1])
    return ans
for _ in range(int(input())):
    print(solve())

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

def solve(n, m, arr):
    arr = [[row[i] for row in arr] for i in range(len(arr[0]))]
    for x in arr:
        x.sort(reverse=True)
    ans = 0
    for x in arr:
        l = len(x)
        for i in range(l):
            ans += (l - 2 * i - 1) * x[i]
    print(ans)

def main():
    for t in range(int(input())):
        (n, m) = map(int, input().split())
        arr = []
        for i in range(n):
            tmp = list(map(int, list(input().split())))
            arr.append(tmp)
        solve(n, m, arr)
threading.stack_size(2 * 10 ** 8)
t = threading.Thread(target=main)
t.start()
t.join()