AquaMoon and Two Arrays (Codeforces 1546A)
Tags: Greedy, brute force

AquaMoon and Cirno are playing an interesting game with arrays. Cirno has prepared two arrays $$$a$$$ and $$$b$$$, both consist of $$$n$$$ non-negative integers. AquaMoon can perform the following operation an arbitrary number of times (possibly zero):  She chooses two indices $$$i$$$ and $$$j$$$ ($$$1 \le i, j \le n$$$), then decreases the $$$i$$$-th element of array $$$a$$$ by $$$1$$$, and increases the $$$j$$$-th element of array $$$a$$$ by $$$1$$$. The resulting values at $$$i$$$-th and $$$j$$$-th index of array $$$a$$$ are $$$a_i - 1$$$ and $$$a_j + 1$$$, respectively. Each element of array $$$a$$$ must be non-negative after each operation. If $$$i = j$$$ this operation doesn't change the array $$$a$$$. AquaMoon wants to make some operations to make arrays $$$a$$$ and $$$b$$$ equal. Two arrays $$$a$$$ and $$$b$$$ are considered equal if and only if $$$a_i = b_i$$$ for all $$$1 \leq i \leq n$$$.Help AquaMoon to find a sequence of operations that will solve her problem or find, that it is impossible to make arrays $$$a$$$ and $$$b$$$ equal.Please note, that you don't have to minimize the number of operations.

Input: The input consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 100$$$) — the number of test cases.The first line of each test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 100$$$).The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \leq a_i \leq 100$$$). The sum of all $$$a_i$$$ does not exceed $$$100$$$.The third line of each test case contains $$$n$$$ integers $$$b_1, b_2, \dots, b_n$$$ ($$$0 \leq b_i \leq 100$$$). The sum of all $$$b_i$$$ does not exceed $$$100$$$.

Output: For each test case print "-1" on the only line if it is impossible to make two arrays equal with some sequence of operations.Otherwise, print an integer $$$m$$$ ($$$0 \leq m \leq 100$$$) in the first line — the number of operations. Then print $$$m$$$ lines, each line consists of two integers $$$i$$$ and $$$j$$$ — the indices you choose for the operation.It can be proven that if it is possible to make two arrays equal with some sequence of operations, there exists a sequence with $$$m \leq 100$$$.If there are multiple possible solutions, you can print any.

Note: In the first example, we do the following operations:  $$$i = 2$$$, $$$j = 1$$$: $$$[1, 2, 3, 4] \rightarrow [2, 1, 3, 4]$$$;  $$$i = 3$$$, $$$j = 1$$$: $$$[2, 1, 3, 4] \rightarrow [3, 1, 2, 4]$$$; In the second example, it's impossible to make two arrays equal.

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

Sample Outputs:
2
2 1
3 1
-1
0
6
1 4
1 4
1 5
1 5
2 5
2 5

Solution (Python):
""""""
import math

def slv():
    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    if sum(a) != sum(b):
        print(-1)
        return
    (x, y) = (0, 0)
    (a1, b1) = ([], [])
    for i in range(n):
        d = a[i] - b[i]
        if d != 0 and d > 0:
            x += d
            while d:
                d -= 1
                a1.append(i + 1)
        elif d != 0 and d < 0:
            d = abs(d)
            y += d
            while d:
                b1.append(i + 1)
                d -= 1
    if x == y:
        print(x)
        for i in range(x):
            print(a1[i], b1[i])
    else:
        print(-1)
if __name__ == '__main__':
    t = 1
    t = int(input())
    while t > 0:
        slv()
        t -= 1

Solution (Python):
def solve(n, a, b):
    if sum(a) != sum(b):
        return [[-1, -1]]
    under = [j for j in range(n) if a[j] < b[j]]
    over = [i for i in range(n) if a[i] > b[i]]
    operations = []
    i_ptr = 0
    j_ptr = 0
    while i_ptr < len(over) and j_ptr < len(under):
        i = over[i_ptr]
        j = under[j_ptr]
        operations.append([i + 1, j + 1])
        a[i] -= 1
        a[j] += 1
        if a[i] == b[i]:
            i_ptr += 1
        if a[j] == b[j]:
            j_ptr += 1
    return operations

def print_solution(solution):
    if solution and solution[0] == [-1, -1]:
        print(-1)
    else:
        print(len(solution))
        for (i, j) in solution:
            print(i, j)

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

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

def main():
    t = int(input().strip())
    for _ in range(t):
        n = int(get_val())
        a = get_seq()
        b = get_seq()
        solution = solve(n, a, b)
        print_solution(solution)
if __name__ == '__main__':
    main()

Solution (Python):
class Solution:

    def __init__(self):
        pass

    def solve(self):
        t = int(input())
        result = []
        for i in range(t):
            n = int(input())
            a = list(map(int, input().split()))
            b = list(map(int, input().split()))
            arr = [0 for j in range(n)]
            if sum(a) != sum(b):
                result.append('-1')
            elif a == b:
                result.append('0')
            else:
                (j, pos, neg, count) = (0, 0, 0, 0)
                s = ''
                for j in range(n):
                    arr[j] = a[j] - b[j]
                total = sum([k for k in arr if k > 0])
                while count < total:
                    if arr[pos] <= 0:
                        while pos < n:
                            if arr[pos] > 0:
                                break
                            pos += 1
                    if arr[neg] >= 0:
                        while neg < n:
                            if arr[neg] < 0:
                                break
                            neg += 1
                    while arr[pos] > 0 and arr[neg] < 0:
                        arr[pos] -= 1
                        arr[neg] += 1
                        count += 1
                        s += '{} {}\n'.format(pos + 1, neg + 1)
                result.append(str(count) + '\n' + s.rstrip('\n'))
        for x in result:
            print(x)
if __name__ == '__main__':
    sol = Solution()
    sol.solve()