Read problem statements in [Hindi], [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

You are given a sequence $A_{1}, A_{2}, \ldots, A_{N}$ and an integer $K$. Determine if it is possible to reorder the elements of the sequence $A$ into a sequence $B_{1}, B_{2}, \ldots, B_{N}$ and choose a real number $m$ in such a way that for each contiguous subsequence of $B$ with length $K$, the arithmetic average of the elements of this subsequence is $m$. If it is possible, find one such reordered subsequence $B$.

------  Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains two space-separated integers $N$ and $K$.
The second line contains $N$ space-separated integers $A_{1}, A_{2}, \ldots, A_{N}$.

------  Output ------
For each test case, print a single line containing the string "YES" if it is possible to reorder the elements of $A$ in the required way, or "NO" otherwise.

If it is possible, print a second line containing $N$ space-separated integers $B_{1}, B_{2}, \ldots, B_{N}$. If there are multiple solutions, you may print any one.

------  Constraints ------
$1 ≤ T ≤ 1,000$
$1 ≤ K ≤ N ≤ 10^{5}$
$1 ≤ A_{i} ≤ 10^{6}$
the sum of $N$ over all test cases does not exceed $10^{6}$

------  Subtasks ------
Subtask #1 (40 points):
$N ≤ 1,000$
the sum of $N$ over all test cases does not exceed $10,000$

Subtask #2 (60 points): original constraints

------  Example Input ------

2
5 3
1 1 2 2 3
6 2
1 1 1 1 1 2

------  Example Output ------

YES
1 2 3 1 2
NO

Source: codechef | Difficulty: VERY_HARD
Tags: Mathematics

Implementation


Solutions:
from collections import Counter
from operator import itemgetter

def find_x1(num, q):
	a1 = 0
	r1 = num // q
	r2 = num % q
	a2 = r1
	for r3 in range(r1 + 1):
		r4 = r2 % (q + 1)
		if r4 == 0:
			a1 = r2 // (q + 1)
			break
		else:
			a2 -= 1
			r2 += q
	num1 = a1 * (q + 1) + a2 * q
	if num1 != num:
		(a1, a2) = (0, 0)
	return (a1, a2)
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split(' '))
	a = [int(x) for x in input().split()]
	if n == k:
		print('YES')
		print(*a)
	else:
		a1 = Counter(a)
		m = n % k
		q = n // k
		q1 = len(a1)
		ans = 'YES'
		if q1 > k:
			ans = 'NO'
		else:
			m1 = 0
			a2 = []
			b1 = []
			b2 = []
			for (k1, v1) in a1.items():
				(x1, y1) = find_x1(v1, q)
				if x1 == 0 and y1 == 0:
					ans = 'NO'
					break
				else:
					m1 += x1
					if m1 > m:
						ans = 'NO'
						break
					x2 = y1 // (q + 1)
					x3 = y1 % (q + 1)
					k2 = int(k1)
					w = (k2, x2)
					b1 = b1 + [k2] * x1
					b2 = b2 + [k2] * x3
					a2.append(w)
			if ans == 'YES' and (m - m1) % q != 0:
				ans = 'NO'
			if ans == 'YES':
				a2.sort(key=itemgetter(1), reverse=True)
				remaining = (m - m1) // q
				for i in a2:
					x2 = i[1]
					k2 = i[0]
					if x2 > 0 and x2 < remaining:
						remaining -= x2
						b1 = b1 + [k2] * (x2 * q)
					elif x2 > 0 and remaining > 0:
						b1 = b1 + [k2] * (remaining * q)
						x2 -= remaining
						remaining = 0
						b2 = b2 + [k2] * (x2 * (q + 1))
					elif x2 > 0:
						b2 = b2 + [k2] * (x2 * (q + 1))
				if remaining != 0:
					ans = 'NO'
				else:
					b = b1 + b2
					b = b * q
					b = b + b1
		print(ans)
		if ans == 'YES':
			print(*b)


import operator
from math import *
t = int(input())
for y in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	d = dict()
	for i in a:
		if i not in d:
			d[i] = 1
		else:
			d[i] += 1
	c = ceil(n / k)
	ch = []
	ch1 = []
	count = 0
	for i in d.keys():
		noh = []
		nol = []
		while d[i]:
			if d[i] % c == 0:
				noh.insert(0, i)
				d[i] -= c
				count += 1
			elif d[i] % (c - 1) == 0:
				nol.append(i)
				d[i] -= c - 1
				count += 1
			elif d[i] > c:
				noh.insert(0, i)
				d[i] -= c
				count += 1
			else:
				print('NO')
				break
		else:
			if noh:
				ch.append(noh)
			if nol:
				ch1.append(nol)
			continue
		break
	else:
		if count > k:
			print('NO')
		else:
			while k - count:
				for i in ch:
					if len(i) >= c - 1:
						ch1.append([i[0]] * c)
						for z in range(c - 1):
							del i[0]
						count += 1
						break
				else:
					break
			if k == count:
				print('YES')
				ch2 = []
				for i in ch:
					ch2.extend(i)
				for i in ch1:
					ch2.extend(i)
				for i in range(n):
					print(ch2[i % k], end=' ')
				print()
			else:
				print('NO')