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

Chef owns $N$ cats (numbered $1$ through $N$) and he wants to feed them. There are $M$ identical cans of cat food; each can must be used to feed exactly one cat and Chef can only feed one cat at a time. Chef wrote down the order in which he wants to feed the cats: a sequence $A_{1}, A_{2}, \ldots, A_{M}$.

An order of feeding cats is *fair* if there is no moment where Chef feeds a cat that has already been fed strictly more times than some other cat. Help Chef — tell him if the order in which he wants to feed the cats is fair.

------  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 $M$. 
The second line contains $M$ space-separated integers $A_{1}, A_{2}, \ldots, A_{M}$.

------  Output ------
For each test case, print a single line containing the string "YES" if the order is fair or "NO" if it is unfair.

------  Constraints ------
$1 ≤ T ≤ 100$
$2 ≤ N ≤ 100$
$1 ≤ M ≤ 10^{3}$

------  Subtasks ------
Subtask #1 (100 points): original constraints

----- Sample Input 1 ------ 
7
3 9
1 2 3 1 2 3 1 2 3
3 9
1 2 3 3 2 1 1 2 3
3 5
2 3 1 1 2
3 6
2 1 1 3 2 3
2 8
1 2 1 2 1 2 1 1
5 3
5 3 1
4 5
1 2 3 1 4
----- Sample Output 1 ------ 
YES
YES
YES
NO
NO
YES
NO
----- explanation 1 ------ 
Example case 4: Cat $1$ will eat twice before cat $3$ eats even once, so the order is unfair.

Example case 5: The order is unfair because cat $1$ will eat its fifth can before cat $2$ eats its fourth can.

Example case 7: The order is unfair because cat $1$ will eat twice before cat $4$ eats even once.

Source: codechef | Difficulty: EASY
Tags: Complete search

Constructive algorithms

Implementation

Ad-hoc


Solutions:
from collections import Counter
t = int(input())
for ni in range(t):
	(n, m) = map(int, input().split())
	l = [i for i in input().split()]
	c = 0
	for i in range(0, m, n):
		x = l[i:i + n]
		if len(x) != len(list(set(x))):
			print('NO')
			c = 1
			break
	if c == 0:
		print('YES')


for i in range(int(input())):
	(n, l) = map(int, input().split())
	L = list(map(int, input().split()))
	for i in range(0, l, n):
		A = L[i:i + n]
		if len(A) != len(set(A)):
			print('NO')
			break
	else:
		print('YES')


testcases = int(input())
while testcases > 0:
	testcases = testcases - 1
	(n, f) = map(int, input().split(' '))
	a = list(map(int, input().split(' ')))
	i = 0
	j = 0
	fla = 0
	while i < f:
		if j % n == 0:
			l = []
			l.append(a[i])
		elif a[i] in l:
			fla = 1
			break
		else:
			l.append(a[i])
		i = i + 1
		j = j + 1
	if fla == 1:
		print('NO')
	else:
		print('YES')


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = [int(x) for x in input().split()]
	ans = 'YES'
	for i in range(0, m, n):
		b = a[i:i + n]
		if i + n < m:
			if len(list(set(b))) != n:
				ans = 'NO'
				break
		elif len(b) != len(list(set(b))):
			ans = 'NO'
	print(ans)


for i in range(int(input())):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	l = []
	for i in range(len(a)):
		l.append(a[:i + 1].count(a[i]))
	lst = []
	for i in range(0, m, n):
		lst.append(l[i:i + n])
	for k in range(len(lst)):
		x = all([lst[k][0] == lst[k][i] for i in range(len(lst[k]))])
		if x != True:
			print('NO')
			break
	else:
		print('YES')


for _ in range(int(input())):
	(b, c) = map(int, input().split())
	arr = list(map(int, input().split()))
	aa = [0] * b
	d = 1
	for i in arr:
		aa[i - 1] += 1
		if max(aa) - min(aa) > 1:
			d = 0
			break
	if d == 1:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	for i in range(0, m, n):
		l = a[i:i + n]
		if len(l) != len(set(l)):
			print('NO')
			break
	else:
		print('YES')


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	seq = [int(i) for i in input().split()]
	(record, ct) = ([], 0)
	for cat_no in seq:
		if cat_no in record:
			print('NO')
			ct = -1
			break
		record.append(cat_no)
		ct += 1
		if ct == n:
			ct = 0
			record = []
	if ct != -1:
		print('YES')


t = int(input())
for t in range(t):
	(n, m) = [int(i) for i in input().split()]
	arr = [int(i) for i in input().split()]
	flag = 1
	i = 0
	while i < m:
		l = arr[i:i + n]
		if len(l) != len(set(l)):
			flag = 0
			break
		i = i + n
	if flag == 1:
		print('YES')
	else:
		print('NO')


for i in range(int(input())):
	(n, m) = [int(x) for x in input().split()]
	a = [int(x) for x in input().split()]
	l1 = []
	flag = 0
	i = 0
	if n == m:
		for i in range(n):
			if i + 1 not in a:
				print('NO')
				break
	elif n > m:
		for i in a:
			if i in l1:
				print('NO')
				break
			else:
				l1.append(i)
		print('YES')
	elif n < m:
		while i + n < m:
			l1 = a[i:i + n:1]
			for k in range(n):
				if k + 1 not in l1:
					print('NO')
					flag = 1
					break
			if flag != 1:
				i += n
			else:
				break
		if flag != 1:
			l1 = []
			for k in a[i:]:
				if k in l1:
					print('NO')
					flag = 2
				else:
					l1.append(k)
			if flag != 2:
				print('YES')


for _ in range(int(input())):
	(N, M) = map(int, input().split())
	L = list(map(int, input().split()))
	for i in range(0, M, N):
		l = L[i:i + N]
		if len(l) != len(set(l)):
			print('NO')
			break
	else:
		print('YES')


for i in range(int(input())):
	(n, m) = map(int, input().split())
	l = list(map(int, input().split()))
	l1 = []
	count = 0
	if len(l) <= n:
		if len(set(l)) == len(l):
			print('YES')
		else:
			print('NO')
	else:
		r = int(len(l) / n)
		c = 0
		for j in range(r):
			l1 = l[c:c + n]
			if len(set(l1)) != n:
				count = 1
				break
			c = c + n
		if len(l) > r * n:
			l1 = l[c:]
			if len(set(l1)) != len(l1):
				count = 1
		if count == 1:
			print('NO')
		else:
			print('YES')


for a in range(int(input())):
	(N, M) = map(int, input().split())
	l = list(map(int, input().split()))
	emp = []
	for i in range(N):
		emp.append(0)
	for el in l:
		if min(emp) == emp[el - 1]:
			emp[el - 1] += 1
		else:
			print('NO')
			break
	else:
		print('YES')


t = input()
for c in range(0, int(t)):
	(n, m) = input().split()
	cats = []
	fair = 1
	for x in range(0, int(n)):
		cats.append(0)
	a = input().split()
	arr = []
	for y in a:
		arr.append(int(y))
	for z in range(0, int(m)):
		cats[arr[z] - 1] = cats[arr[z] - 1] + 1
		if max(cats) > min(cats) + 1:
			print('NO')
			fair = 0
			break
	if fair == 1:
		print('YES')


tests = int(input())
for i in range(tests):
	(n, m) = map(int, input().split())
	arr = list(map(int, input().split()))
	ans = [0] * n
	fair = 'YES'
	for j in arr:
		ans[j - 1] += 1
		if max(ans) - min(ans) > 1:
			fair = 'NO'
			break
	print(fair)


for _ in range(int(input())):
	(a, b) = map(int, input().split())
	l = list(map(int, input().split()))
	(s, d) = (1, {})
	for i in l:
		if i not in d:
			d[i] = 1
		else:
			d[i] += 1
		ma = max(d.values())
		mi = min(d.values())
		s = max(s, d[i])
		if ma - mi > 1 or s > d[i]:
			print('NO')
			break
	else:
		print('YES')


for t in range(int(input())):
	(n, m) = map(int, input().split())
	l = list(map(int, input().split()))
	b = []
	for i in range(n):
		b.append(0)
	f = 1
	for i in l:
		b[i - 1] += 1
		ma = max(b)
		mi = min(b)
		if ma - mi > 1:
			f = 0
			break
	if f == 1:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	c = [0] * n
	ans = 1
	for i in a:
		c[i - 1] += 1
		if max(c) - min(c) >= 2:
			ans = 0
	if ans == 1:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	arr = [int(i) for i in input().split()]
	if n >= m:
		if len(set(arr)) == m:
			print('YES')
		else:
			print('NO')
	else:
		k = m // n
		flag = False
		for i in range(k):
			if len(set(arr[i * n:i * n + n])) == n:
				continue
			else:
				flag = True
		if len(set(arr[k * n:m])) != m - k * n:
			flag = True
		if flag:
			print('NO')
		else:
			print('YES')


n = int(input())
NandM = []
testCases = []
for i in range(n):
	NandM.append(list(map(int, input().split())))
	testCases.append(list(map(int, input().split())))

def resFuc(i, j):
	temp = [0] * i[0]
	for k in j:
		temp[k - 1] += 1
		a = temp[k - 1] - 2
		if a in temp:
			return 'NO'
	return 'YES'
for (i, j) in zip(NandM, testCases):
	print(resFuc(i, j))


t = int(input())
for o in range(t):
	(c, n) = list(map(int, input().split()))
	arr = list(map(int, input().split()))
	d = {}
	for i in arr:
		d[i] = 0
	u = 0
	for i in arr:
		d[i] = d[i] + 1
		if min(d.values()) < d[i] - 1:
			u = 9
			break
	if u == 9:
		print('NO')
	else:
		print('YES')


tc = int(input())
while tc:
	fl = False
	(x, y) = map(int, input().split())
	li = list(map(int, input().split()))
	for itr in range(0, len(li) - x + 1, x):
		sm = li[itr:itr + x]
		if len(set(sm)) != x:
			fl = True
	if fl == True:
		print('NO')
	else:
		print('YES')
	tc = tc - 1


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	arr = list(map(int, input().split()))
	cat = [0] * n
	ans = 'YES'
	for items in arr:
		cat[items - 1] += 1
		if max(cat) - min(cat) >= 2:
			ans = 'NO'
			break
	print(ans)


t = int(input())
while t:
	(n, m) = [int(i) for i in input().split()]
	a = [int(i) for i in input().split()]
	d = {i: 0 for i in range(1, n + 1)}
	found = True
	for val in a:
		d[val] += 1
		for item in d:
			if d[val] - d[item] > 1:
				found = False
				break
		if not found:
			break
	if found:
		print('YES')
	else:
		print('NO')
	t -= 1


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	li = list(map(int, input().split()))
	for i in range(0, m, n):
		s = set(li[i:i + n])
		if i + n > m:
			if len(s) != n - (i + n - m):
				print('NO')
				break
		elif len(s) < n:
			print('NO')
			break
	else:
		print('YES')


def fairness(*args):
	(n, m, li) = args
	nextcat = [i for i in range(1, n + 1)]
	for i in li:
		if i not in nextcat:
			return 'NO'
		nextcat.remove(i)
		if len(nextcat) == 0:
			nextcat = [i for i in range(1, n + 1)]
	return 'YES'

def loop():
	for _ in range(int(input())):
		(n, m) = map(int, input().split())
		li = list(map(int, input().split()))
		print(fairness(n, m, li))
loop()


T = int(input())
for _ in range(T):
	(N, M) = map(int, input().split())
	li = list(map(int, input().split()))
	d = {}
	flag = True
	for j in range(1, N + 1):
		d[j] = 0
	for k in li:
		d[k] += 1
		if min(d.values()) < d[k] - 1:
			print('NO')
			flag = False
			break
		else:
			continue
	if flag == True:
		print('YES')


success = 'YES'
failure = 'NO'

def solve(*args):
	(n, m, a) = args
	a = a[::-1]
	nextfeed = [x + 1 for x in range(n)]
	while len(a) > 0:
		nextcat = a.pop()
		if nextcat not in nextfeed:
			return failure
		nextfeed.remove(nextcat)
		if len(nextfeed) == 0:
			nextfeed = [x + 1 for x in range(n)]
	return success

def do_codechef():
	for t in range(int(input())):
		(n, m) = map(int, input().split(' '))
		a = list(map(int, input().split(' ')))
		print(solve(n, m, a))
do_codechef()
exit()


T = int(input())
for tj in range(T):
	(N, M) = map(int, input().split())
	integers = list(map(int, input().split()))
	cats = [0] * N
	flag = False
	for i in range(M):
		cats[integers[i] - 1] += 1
		if max(cats) - min(cats) > 1:
			flag = True
			break
	if flag == True:
		print('NO')
	else:
		print('YES')


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	ct = 0
	ans = [0] * n
	flag = 0
	arr = list(map(int, input().split()))
	for i in range(len(arr)):
		ans[arr[i] - 1] += 1
		if max(ans) - min(ans) > 1:
			flag = 1
			break
	if flag == 0:
		print('YES')
	else:
		print('NO')


t = int(input())
for i in range(t):
	(n, m) = map(int, input().split(' '))
	k = [0] * n
	ans = 'YES'
	a = [int(i) for i in input().split(' ')]
	for i in range(m):
		k[a[i] - 1] += 1
		if max(k) - min(k) >= 2:
			ans = 'NO'
			break
	print(ans)


def solve():
	(n, m) = [int(i) for i in input().split()]
	a = [int(i) for i in input().split()]
	for i in range(0, m - m % n, n):
		for j in range(1, n + 1):
			if a[i:i + n].count(j) > 1:
				return 'NO'
	for j in range(1, n + 1):
		if a[m - m % n:].count(j) > 1:
			return 'NO'
	return 'YES'
t = int(input())
for j in range(t):
	print(solve())


t = int(input())
for _ in range(t):
	(n, m) = [int(x) for x in input().split()]
	L = [int(x) for x in input().split()]
	ans = 'YES'
	while L:
		L2 = L[:n]
		if len(L2) != len(set(L2)):
			ans = 'NO'
			break
		L = L[n:]
	print(ans)


from math import ceil
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	arr = [i + 1 for i in range(n)]
	l1 = list(map(int, input().split()))
	a = []
	try:
		for i in l1:
			if len(a) == 0:
				a = arr.copy()
			a.remove(i)
	except:
		print('NO')
	else:
		print('YES')


for i in range(int(input())):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	f = 1
	for j in range(0, m - n + 1, n):
		p = a[j:j + n]
		if len(set(p)) == n:
			continue
		else:
			f = 0
			break
	if f == 0:
		print('NO')
	else:
		print('YES')


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	lst = list(map(int, input().split()))
	x = [0] * n
	ans = 'YES'
	for items in lst:
		x[items - 1] += 1
		if max(x) - min(x) >= 2:
			ans = 'NO'
			break
	print(ans)


for t in range(int(input())):
	(n, m) = map(int, input().split())
	l = list(map(int, input().split()))
	c = [0] * n
	res = 'YES'
	for i in l:
		c[i - 1] += 1
		if max(c) - min(c) >= 2:
			res = 'NO'
			break
	print(res)


for t in range(int(input())):
	(n, m) = map(int, input().split())
	l1 = list(map(int, input().split()))
	d = dict()
	flag = 1
	for ele in l1:
		if ele in d:
			continue
		else:
			d[ele] = 0
	for i in l1:
		if i in d:
			d[i] += 1
			if d[max(zip(d.values(), d.keys()))[1]] - d[min(zip(d.values(), d.keys()))[1]] >= 2:
				flag = 0
				break
	if flag == 0:
		print('NO')
	else:
		print('YES')


for i in range(int(input())):
	(n, m) = map(int, input().split())
	l = list(map(int, input().split()))
	a = list([0] * n)
	f = 1
	for i in l:
		a[i - 1] += 1
		ma = min(a)
		mx = max(a)
		if mx - ma >= 2:
			f = 0
			break
	if f == 1:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	l = list(map(int, input().split()))
	a = list([0] * n)
	flag = 1
	for i in l:
		a[i - 1] += 1
		min_a = min(a)
		max_a = max(a)
		if max_a - min_a >= 2:
			flag = 0
			break
	if flag == 1:
		print('YES')
	else:
		print('NO')


def solve(arr, n, m):
	feed = [0] * n
	for i in range(m):
		cat = arr[i] - 1
		if feed[cat] == 1:
			return False
		feed[cat] = 1
		if (i + 1) % n == 0:
			feed = [0] * n
	return True

def main():
	for _ in range(int(input())):
		(n, m) = map(int, input().split())
		arr = list(map(int, input().split()))
		if solve(arr, n, m):
			print('YES')
		else:
			print('NO')
main()


for _ in range(int(input())):
	(m, n) = map(int, input().split())
	arr = list([0] * m)
	arr_in = list(map(int, input().split()))
	flag = 1
	for i in arr_in:
		arr[i - 1] += 1
		min_ele = min(arr)
		max_ele = max(arr)
		if max_ele - min_ele >= 2:
			flag = 0
			break
	if flag == 1:
		print('YES')
	else:
		print('NO')


t = int(input())
for u in range(t):
	(n, m) = map(int, input().split())
	l = list(map(int, input().split()))
	for i in range(m):
		if (i + 1) % n == 1:
			d = {}
			f = True
		if l[i] in d:
			f = False
			break
		else:
			d[l[i]] = 0
	if f:
		print('YES')
	else:
		print('NO')


t = int(input())
for u in range(t):
	(n, m) = map(int, input().split())
	l = list(map(int, input().split()))
	flag = True
	for i in range(0, m, n):
		l1 = l[i:i + n]
		d = {}
		for j in l1:
			if j not in d:
				d[j] = 1
			else:
				d[j] += 1
		for i in l1:
			if d[i] == 1:
				flag = True
			else:
				flag = False
				break
		if flag == False:
			break
	if flag == False:
		print('NO')
	else:
		print('YES')


t = int(input())
for u in range(t):
	(n, m) = map(int, input().split())
	l = list(map(int, input().split()))
	flag = True
	temp = True
	x = m % n
	y = m - x
	l2 = l[y:]
	for i in l2:
		if l2.count(i) > 1:
			temp = False
			break
	for i in range(0, y, n):
		l1 = l[i:i + n]
		d = {}
		for j in range(len(l1)):
			if l1[j] not in d:
				d[l1[j]] = 1
			else:
				d[l1[j]] += 1
		s = list(set(l1))
		for j in range(len(s)):
			if d[s[j]] == 1:
				flag = True
			else:
				flag = False
				break
		if flag == False:
			break
	if flag == False or temp == False:
		print('NO')
	else:
		print('YES')


T = int(input())
for t in range(T):
	(n, m) = map(int, input().split())
	b = list(map(int, input().split()))
	flag = 0
	a = [0] * n
	for i in b:
		a[i - 1] += 1
		if max(a) - min(a) == 2:
			print('NO')
			flag = 1
			break
	if flag == 0:
		print('YES')


n = int(input())
for j in range(n):
	(N, M) = map(int, input().split())
	l = list(map(int, input().split()))
	c = [0] * N
	res = 'YES'
	for i in l:
		c[i - 1] += 1
		if max(c) - min(c) >= 2:
			res = 'NO'
			break
	print(res)


T = int(input())
for t in range(T):
	(N, M) = map(int, input().split())
	arr = list(map(int, input().split()))
	c = [0] * N
	res = 'YES'
	for i in arr:
		c[i - 1] += 1
		if max(c) - min(c) >= 2:
			res = 'NO'
			break
	print(res)


for i in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	a = [0] * n
	d = 1
	for i in l:
		a[i - 1] += 1
		if max(a) - min(a) > 1:
			d = 0
			break
	if d == 1:
		print('YES')
	else:
		print('NO')


total_testcases = int(input())
for testcase in range(total_testcases):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	d = {}
	ans = True
	f = [0] * n
	for value in a:
		f[value - 1] += 1
		if max(f) - min(f) > 1:
			ans = False
			break
	print('YES' if ans else 'NO')