Phoenix and Beauty (Codeforces 1348B)
Tags: Greedy, sortings

Phoenix loves beautiful arrays. An array is beautiful if all its subarrays of length $$$k$$$ have the same sum. A subarray of an array is any sequence of consecutive elements.Phoenix currently has an array $$$a$$$ of length $$$n$$$. He wants to insert some number of integers, possibly zero, into his array such that it becomes beautiful. The inserted integers must be between $$$1$$$ and $$$n$$$ inclusive. Integers may be inserted anywhere (even before the first or after the last element), and he is not trying to minimize the number of inserted integers.

Input: The input consists of multiple test cases. The first line contains an integer $$$t$$$ ($$$1 \le t \le 50$$$) — the number of test cases.The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le k \le n \le 100$$$).The second line of each test case contains $$$n$$$ space-separated integers ($$$1 \le a_i \le n$$$) — the array that Phoenix currently has. This array may or may not be already beautiful.

Output: For each test case, if it is impossible to create a beautiful array, print -1. Otherwise, print two lines.The first line should contain the length of the beautiful array $$$m$$$ ($$$n \le m \le 10^4$$$). You don't need to minimize $$$m$$$.The second line should contain $$$m$$$ space-separated integers ($$$1 \le b_i \le n$$$) — a beautiful array that Phoenix can obtain after inserting some, possibly zero, integers into his array $$$a$$$. You may print integers that weren't originally in array $$$a$$$.If there are multiple solutions, print any. It's guaranteed that if we can make array $$$a$$$ beautiful, we can always make it with resulting length no more than $$$10^4$$$.

Note: In the first test case, we can make array $$$a$$$ beautiful by inserting the integer $$$1$$$ at index $$$3$$$ (in between the two existing $$$2$$$s). Now, all subarrays of length $$$k=2$$$ have the same sum $$$3$$$. There exists many other possible solutions, for example:   $$$2, 1, 2, 1, 2, 1$$$  $$$1, 2, 1, 2, 1, 2$$$ In the second test case, the array is already beautiful: all subarrays of length $$$k=3$$$ have the same sum $$$5$$$.In the third test case, it can be shown that we cannot insert numbers to make array $$$a$$$ beautiful.In the fourth test case, the array $$$b$$$ shown is beautiful and all subarrays of length $$$k=4$$$ have the same sum $$$10$$$. There exist other solutions also.

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

Sample Outputs:
5
1 2 1 2 1
4
1 2 2 1
-1
7
4 3 2 1 4 3 2

Solution (Python):
for ii in range(int(input())):
    (n, k) = map(int, input().split())
    s = [int(i) for i in input().split()]
    e = {i for i in s}
    d = []
    if len(s) == 1:
        print(1)
        print(*s)
    elif len(e) > k:
        print(-1)
    else:
        r = [str(i) for i in e]
        a = ''
        if len(r) < k:
            for i in range(k - len(r)):
                r.append(r[0])
        r = ' '.join(r)
        for i in range(n):
            a += r + ' '
        print(n * k)
        print(a)

Solution (Python):
from functools import lru_cache
from collections import defaultdict, deque
from heapq import heappush, heappop

def solution():
    t = int(input())
    for _ in range(t):
        (n, k) = map(int, input().split())
        arr = list(map(int, input().split()))
        syms = list(set(arr))
        if len(syms) > k:
            print('-1')
            continue
        syms += [1] * (k - len(syms))
        res = (' '.join(map(str, syms)) + ' ') * n
        print(n * k)
        print(res)
solution()

Solution (Python):
for i in range(int(input())):
    (n, k) = [int(i) for i in input().split(' ')]
    arr = [int(i) for i in input().split(' ')]
    s = set(arr)
    if len(s) > k:
        print(-1)
    else:
        temp = ' '.join([str(i) for i in s] + ['1'] * (k - len(s)))
        result = ''
        print(n * k)
        for i in range(n):
            result += temp + ' '
        print(result)