MEX and Increments (Codeforces 1619E)
Tags: Greedy, sortings

Dmitry has an array of $$$n$$$ non-negative integers $$$a_1, a_2, \dots, a_n$$$.In one operation, Dmitry can choose any index $$$j$$$ ($$$1 \le j \le n$$$) and increase the value of the element $$$a_j$$$ by $$$1$$$. He can choose the same index $$$j$$$ multiple times.For each $$$i$$$ from $$$0$$$ to $$$n$$$, determine whether Dmitry can make the $$$\mathrm{MEX}$$$ of the array equal to exactly $$$i$$$. If it is possible, then determine the minimum number of operations to do it.The $$$\mathrm{MEX}$$$ of the array is equal to the minimum non-negative integer that is not in the array. For example, the $$$\mathrm{MEX}$$$ of the array $$$[3, 1, 0]$$$ is equal to $$$2$$$, and the array $$$[3, 3, 1, 4]$$$ is equal to $$$0$$$.

Input: The first line of input data contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases in the input. The descriptions of the test cases follow.The first line of the description of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the length of the array $$$a$$$.The second line of the description of each test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le n$$$) — elements of the array $$$a$$$.It is guaranteed that the sum of the values $$$n$$$ over all test cases in the test does not exceed $$$2\cdot10^5$$$.

Output: For each test case, output $$$n + 1$$$ integer — $$$i$$$-th number is equal to the minimum number of operations for which you can make the array $$$\mathrm{MEX}$$$ equal to $$$i$$$ ($$$0 \le i \le n$$$), or -1 if this cannot be done.

Note: In the first set of example inputs, $$$n=3$$$:  to get $$$\mathrm{MEX}=0$$$, it is enough to perform one increment: $$$a_1$$$++;  to get $$$\mathrm{MEX}=1$$$, it is enough to perform one increment: $$$a_2$$$++;  $$$\mathrm{MEX}=2$$$ for a given array, so there is no need to perform increments;  it is impossible to get $$$\mathrm{MEX}=3$$$ by performing increments. 

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

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

Solution (Python):
import sys, io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def mex_and_increments(n, a):
    a.sort()
    s = [-1]
    total = 0
    cursor = 0
    output = [-1] * (n + 1)
    for i in range(n + 1):
        if len(s) == 0:
            break
        v = s.pop()
        total += i - 1 - v
        local_shift = 0
        while cursor < n and a[cursor] == i:
            s += [i]
            cursor += 1
            local_shift += 1
        output[i] = total + local_shift
    return ' '.join(map(str, output))
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    sys.stdout.write(f'{mex_and_increments(n, a)}\n')

Solution (Python):
from collections import defaultdict
t = int(input())
for _ in range(t):
    _ = input()
    inp = [int(el) for el in input().split()]
    nums = defaultdict(int)
    for el in inp:
        nums[el] += 1
    stack = []
    max_mex = None
    curr_cost = 0
    res = []
    for i in range(len(inp) + 1):
        if max_mex is not None:
            res.append('-1')
        else:
            stack.extend([i] * nums[i])
            res.append(str(curr_cost + nums[i]))
            if len(stack) == 0:
                max_mex = i
            else:
                curr_cost += i - stack[-1]
                stack.pop()
    print(' '.join(res))

Solution (Python):
t = int(input())
for _ in range(t):
    n = int(input())
    cot = [0] * (n + 1)
    s = input().split()
    nums = [int(x) for x in s]
    for num in nums:
        cot[num] += 1
    pre = 0
    cur = 0
    v = []
    ans = []
    for i in range(n + 1):
        if pre < i:
            ans.append(-1)
            while len(ans) < n + 1:
                ans.append(-1)
            break
        else:
            ans.append(cur + cot[i])
            if cot[i] == 0 and len(v) > 0:
                cur += i - v[-1]
                v.pop()
            else:
                j = 1
                while j <= cot[i] - 1:
                    v.append(i)
                    j += 1
        pre += cot[i]
    res = ' '.join([str(a) for a in ans])
    print(res)