Same Count One (Codeforces 1774D)
Tags: Greedy, two pointers

ChthollyNotaSeniorious received a special gift from AquaMoon: $$$n$$$ binary arrays of length $$$m$$$. AquaMoon tells him that in one operation, he can choose any two arrays and any position $$$pos$$$ from $$$1$$$ to $$$m$$$, and swap the elements at positions $$$pos$$$ in these arrays.He is fascinated with this game, and he wants to find the minimum number of operations needed to make the numbers of $$$1$$$s in all arrays the same. He has invited you to participate in this interesting game, so please try to find it!If it is possible, please output specific exchange steps in the format described in the output section. Otherwise, please output $$$-1$$$.

Input: The first line of the input contains a single integer $$$t$$$ ($$$1 \leq t \leq 2\cdot 10^4$$$)  — the number of test cases. The description of test cases follows.The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$2 \leq n \leq 10^5$$$, $$$2 \leq m \leq 10^5$$$).The $$$i$$$-th of the following $$$n$$$ lines contains $$$m$$$ integers $$$a_{i, 1}, a_{i, 2}, \ldots, a_{i, m}$$$ $$$(0 \le a_{i, j} \le 1)$$$  — the elements of the $$$i$$$-th array. It is guaranteed that the sum of $$$n \cdot m$$$ over all test cases does not exceed $$$10^6$$$.

Output: For each test case, if the objective is not achievable, output $$$-1$$$. Otherwise, in the first line output $$$k$$$ $$$(0 \le k \le mn)$$$  — the minimum number of operations required.The $$$i$$$-th of the following $$$k$$$ lines should contain $$$3$$$ integers, $$$x_i, y_i, z_i$$$ $$$(1 \le x_i, y_i \le n, 1 \le z_i \le m)$$$, which describe an operation that swap $$$a_{x_i, z_i}, a_{y_i, z_i}$$$: swap the $$$z_i$$$-th number of the $$$x_i$$$-th and $$$y_i$$$-th arrays.

Note: In the first test case, it's enough to do a single operation: to swap the first element in the second and the first rows. The arrays will become $$$[0, 1, 1, 0], [1, 0, 1, 0], [1, 0, 0, 1]$$$, each of them contains exactly two $$$1$$$s.

Sample Inputs:
3
3 4
1 1 1 0
0 0 1 0
1 0 0 1
4 3
1 0 0
0 1 1
0 0 1
0 0 0
2 2
0 0
0 1

Sample Outputs:
1
2 1 1
1
4 2 2
-1

Solution (Python):
import itertools
import math
import threading
import time
from builtins import input, range
from math import gcd as gcd
import sys
from io import BytesIO, IOBase
import queue
import itertools
import collections
from heapq import heappop, heappush
import random
import os
from random import randint
import decimal
from math import factorial as fac
DEBUG = [False]

def debug(*args):
    if DEBUG[0]:
        print(*args)

def solve():
    (n, m) = map(int, sys.stdin.readline().split())
    a = [list(map(int, sys.stdin.readline().split())) for i in range(n)]
    ones = [[0, i] for i in range(n)]
    s = 0
    for i in range(n):
        r = 0
        for j in range(m):
            r += a[i][j]
        s += r
        ones[i][0] = r
    if s % n != 0:
        sys.stdout.write('-1\n')
        return
    e = s // n
    ones.sort(key=lambda x: -x[0])
    res_len = 0
    res = ''
    l = n - 1
    r = 0
    while r < l:
        if ones[r][0] == ones[l][0]:
            break
        need_to_add_down = e - ones[l][0]
        can_take_up = ones[r][0] - e
        r0 = ones[r][1]
        l0 = ones[l][1]
        for j in range(m):
            if a[r0][j] > a[l0][j]:
                res_len += 1
                res += str(r0 + 1) + ' ' + str(l0 + 1) + ' ' + str(j + 1) + '\n'
                a[r0][j] = 0
                a[l0][j] = 1
                ones[r][0] -= 1
                ones[l][0] += 1
                need_to_add_down -= 1
                can_take_up -= 1
                if need_to_add_down == 0 or can_take_up == 0:
                    break
        if need_to_add_down == 0:
            l -= 1
        if can_take_up == 0:
            r += 1
    sys.stdout.write(str(res_len) + '\n' + res)
    return
if __name__ == '__main__':
    multytest = True
    if multytest:
        t = int(sys.stdin.readline())
        for _ in range(t):
            solve()
    else:
        solve()

Solution (Python):
for _ in range(int(input())):
    (n, m) = [int(i) for i in input().split()]
    a = []
    num = [0] * n
    for i in range(n):
        a.append([int(i) for i in input().split()])
        num[i] = a[i].count(1)
    count = sum(num)
    if count % n:
        print(-1)
        continue
    count //= n
    mm = 0
    for i in num:
        if i - count > 0:
            mm += i - count
    print(mm)
    (i, j) = (0, 0)
    while True:
        while i < n and num[i] <= count:
            i += 1
        while j < n and num[j] >= count:
            j += 1
        if i >= n or j >= n:
            break
        m = min(num[i] - count, count - num[j])
        num[i] -= m
        num[j] += m
        f = 0
        while m:
            if a[i][f] == 1 and a[j][f] == 0:
                a[i][f] = 0
                a[j][f] = 1
                print(i + 1, j + 1, f + 1)
                m -= 1
            f += 1

Solution (Python):
for tc in range(int(input())):
    (n, m) = map(int, input().split())
    l = []
    for i in range(n):
        l.append(list(map(int, input().split())))
    c1 = []
    for i in range(n):
        c1.append(l[i].count(1))
    exp1 = sum(c1) // n
    exp0 = m - exp1
    if sum(c1) % n != 0:
        print(-1)
        continue
    elif c1.count(exp1) == n:
        print(0)
        continue
    more = []
    less = []
    for i in range(n):
        if c1[i] > exp1:
            more.append(i)
        elif c1[i] < exp1:
            less.append(i)
    k = 0
    count = 0
    res = []
    i = 0
    while i < len(more):
        for j in range(m):
            if i >= len(more):
                break
            if l[more[i]][j] == 1 and l[less[k]][j] == 0:
                count += 1
                res.append([more[i] + 1, less[k] + 1, j + 1])
                l[more[i]][j] = 0
                l[less[k]][j] = 1
                c1[less[k]] += 1
                c1[more[i]] -= 1
                if c1[less[k]] == exp1:
                    k += 1
                if c1[more[i]] == exp1:
                    i += 1
    print(count)
    for i in res:
        print(i[0], end=' ')
        print(i[1], end=' ')
        print(i[2], end=' ')
        print()