Read problems statements in Mandarin Chinese  and Russian. 

Alok-nath is man of equality. He needs your help to divide his “sanskars” evenly amongst all his followers. By doing this, Alok-nath can create equality amongst his followers and he'll be called a true “sanskari”.

Alok-nath has N sanskars, and K followers. Each sanskar is given a numerical value which shows its intensity.

Your task is to determine whether it is possible to allocate all the sanskars to followers in such a way that the sum of intensities of the sanskars allocated to each follower is equal. Note : A sanskar can be allocated to only one of the followers.

------ Input ------ 

The first line of the input contains an integer T, denoting the number of test cases. Then T test cases follow. The first line of each case contains two integers N and K, with N denoting the number of sanskars and K denoting the number of followers. In the next line are N space separated integers denoting the intensities of each sanskar.

------ Output ------ 

For each test case, output "yes" if it is possible to divide his sanskars equally amongst his followers; otherwise output "no" (without quotes).

------ Constraints ------ 

$1 ≤ T ≤ 10$
$1 ≤ N ≤ 21$
$1 ≤ K ≤ 8$
$Subtask #1 (20 points) : 0 ≤ intensity of sanskar ≤ 10^{5}$
$Subtask #2 (80 points) : 0 ≤ intensity of sanskar ≤ 10^{10}$

----- Sample Input 1 ------ 
2
5 3
1 2 4 5 6
5 3
1 2 4 5 7
----- Sample Output 1 ------ 
yes
no
----- explanation 1 ------ 
In the first case, sanskars can be allocated as follows, each follower receiving a total intensity of 6: {1,5}, {2,4}, {6}.

Source: codechef | Difficulty: HARD
Tags: Dynamic programming

Bit manipulation

Data structures

Mathematics


Solutions:
import sys
sys.setrecursionlimit(10 ** 6)
book = dict()
a = []
n = kk = rs0 = 0

def outc(k, j, v, rs):
	if (k, j, tuple(v)) in book.keys() and rs == rs0:
		return book[k, j, tuple(v)]
	elif rs != 0 and j != n:
		res = False
		if not v[j]:
			if a[j] <= rs:
				w = v.copy()
				w[j] = True
				res = res or outc(k, j + 1, w, rs - a[j])
		res = res or outc(k, j + 1, v, rs)
		book[k, j, tuple(v)] = res
		return res
	elif rs != 0 and j == n:
		return False
	elif rs == 0 and k != kk - 1:
		return outc(k + 1, 0, v, rs0)
	else:
		return True
T = int(input())
for _ in range(T):
	(N, K) = map(int, input().split())
	A = list(map(int, input().split()))
	a = A
	(n, kk) = (N, K)
	mysum = sum(A)
	if N < K or mysum % K != 0:
		print('no')
	else:
		rs0 = mysum // K
		if outc(0, 0, [False] * N, rs0):
			print('yes')
		else:
			print('no')
	book.clear()


def hasSubsetSum(A, V):
	if V == 0:
		return (True, [])
	if len(A) == 0:
		return (False, [])
	if V < A[len(A) - 1]:
		return hasSubsetSum(A[0:len(A) - 1], V)
	else:
		L = [len(A) - 1]
		TMP = hasSubsetSum(A[0:len(A) - 1], V - A[len(A) - 1])
		if TMP[0]:
			TMP[1].append(len(A) - 1)
			return (True, TMP[1])
		else:
			return hasSubsetSum(A[0:len(A) - 1], V)

def hasPartition(A, SSUM, K):
	if K == 0:
		return True
	TMP = hasSubsetSum(A, SSUM)
	if TMP[0]:
		B = [A[j] for j in range(len(A)) if not j in TMP[1]]
		return hasPartition(B, SSUM, K - 1)
	else:
		return False
T = int(input())
for _ in range(T):
	(N, K) = map(int, input().split())
	A = list(map(int, input().split()))
	if K > N:
		print('no')
		continue
	SUM = 0
	for j in range(N):
		SUM = SUM + A[j]
	if SUM % K != 0:
		print('no')
		continue
	SSUM = SUM // K
	if hasPartition(A, SSUM, K):
		print('yes')
	else:
		print('no')


__author__ = 'Rakshak.R.Hegde'
target = 0
san = []

def recurse(i, sum):
	if sum == target:
		return True
	if sum > target or i == len(san):
		return False
	if recurse(i + 1, sum + san[i]):
		del san[i]
		return True
	return recurse(i + 1, sum)
t = int(input())
while t:
	t -= 1
	(n, k) = map(int, input().split())
	san = sorted(map(int, input().split()), reverse=True)
	(target, rem) = divmod(sum(san), k)
	if rem == 0 and san[0] <= target:
		if target == 0:
			print('yes' if n >= k else 'no')
			continue
		possible = True
		for i in range(k):
			if recurse(1, san[0]):
				del san[0]
			else:
				possible = False
				break
		print('yes' if possible else 'no')
	else:
		print('no')


def divide(l, num, dn):
	if dn == 0:
		return True
	if num == -1:
		return False
	if l[num] > dn or l[num] == 0:
		return divide(l, num - 1, dn)
	if divide(l, num - 1, dn - l[num]):
		l[num] = 0
		return True
	return divide(l, num - 1, dn)
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = sorted(list(map(int, input().split())))
	if sum(l) % k != 0 or n < k:
		print('no')
		continue
	dn = sum(l) // k
	ans = False
	if l[n - 1] <= dn:
		ans = True
	for i in range(k):
		if not divide(l, n - 1, dn):
			ans = False
			break
	print('yes') if ans == True else print('no')


def getans(arr, k):
	sm = sum(arr)
	if sm % k != 0 or k > len(arr):
		return 'no'
	if all((i == 0 for i in arr)):
		return 'yes'
	req = sm // k
	visited = [False] * len(arr)
	retval = compute(arr, 0, k, req, visited, req)
	if retval:
		return 'yes'
	return 'no'

def compute(arr, idx, k, req, visited, sm):
	if k == 0:
		return all(visited)
	if req == 0:
		return compute(arr, 0, k - 1, sm, visited, sm)
	state = False
	for i in range(idx, len(arr)):
		if not visited[i] and arr[i] <= req:
			visited[i] = True
			state = compute(arr, i + 1, k, req - arr[i], visited, sm)
			if state:
				return state
			visited[i] = False
	return state
for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	arr = list(map(int, input().split()))
	arr.sort()
	print(getans(arr, k))


import sys

def is_partition(n, tot, count):
	if tot == 0:
		for v in range(count):
			sk.remove(l[v])
		return True
	if tot < 0:
		return False
	if n < 0 and tot != 0:
		return False
	l[count] = sk[n]
	return is_partition(n - 1, tot - sk[n], count + 1) or is_partition(n - 1, tot, count)
t = sys.stdin.readline()
t = int(t)
for j in range(t):
	(n, k) = sys.stdin.readline().split()
	n = int(n)
	k = int(k)
	tot = 0
	sk = []
	l = [None] * n
	p = []
	flag = False
	count = 0
	a = sys.stdin.readline().split()
	if k > n:
		print('no')
		continue
	for i in range(n):
		a[i] = int(a[i])
		sk.append(a[i])
		tot += a[i]
	indv = int(tot / k)
	if tot % k != 0:
		print('no')
		continue
		sk.sort()
	else:
		for i in range(k):
			ans = is_partition(len(sk) - 1, indv, 0)
			if ans == False:
				flag = True
				break
	if flag == False:
		print('yes')
	else:
		print('no')


import math
import bisect

def power(x, y, p):
	res = 1
	x = x % p
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def inn():
	return int(input())

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

def partition(arr, num, ps):
	if ps == 0:
		return True
	if num == 0:
		return False
	if arr[num - 1] > ps or arr[num - 1] == 0:
		return partition(arr, num - 1, ps)
	if partition(arr, num - 1, ps - a[num - 1]):
		arr[num - 1] = 0
		return True
	return partition(arr, num - 1, ps)
MOD = 10 ** 9 + 7
INF = inf = 10 ** 18 + 5
for t in range(int(input())):
	(n, k) = inl()
	a = inl()
	a.sort()
	s = sum(a)
	if s % k != 0 or n < k:
		print('no')
		continue
	ans = False
	ps = s // k
	if a[n - 1] <= ps:
		ans = True
		for i in range(k):
			if not partition(a, n, ps):
				ans = False
				break
	print('yes') if ans else print('no')


from itertools import chain, combinations

def list_powerset(lst, k):
	result = [[]]
	for x in lst:
		result.extend([subset + [x] for subset in result if sum(subset) + x <= k])
	return result

def powerset(iterable, k):
	xs = iterable
	return chain.from_iterable((combinations(xs, n) for n in range(len(xs) - k + 1 + 1)))

def list_powerset2(lst):
	return reduce(lambda result, x: result + [subset + [x] for subset in result], lst, [[]])
T = int(input())
for t in range(T):
	(N, K) = [int(i) for i in input().split()]
	nums = [int(i) for i in input().split() if int(i) != 0]
	d = {}
	for i in nums:
		try:
			d[i] += 1
		except KeyError:
			d[i] = 1
	reach = sum(nums)
	if reach == 0:
		if N >= K:
			print('yes')
		else:
			print('no')
		continue
	if reach % K != 0:
		print('no')
		continue
	reach = int(reach / K)
	subsets = [i for i in list_powerset(nums, reach) if sum(i) == reach]
	n_set = 0
	for i in subsets:
		flag = True
		for j in i:
			if d[j] < 1:
				flag = False
				break
		if flag:
			for j in i:
				d[j] -= 1
			n_set += 1
	flag = True
	for key in d.keys():
		if d[key] > 0:
			flag = False
			break
	if flag and n_set == K:
		print('yes')
	else:
		print('no')


def ret_res(arr, vis_arr, ind, memo, val):
	if (ind, val) in memo:
		return memo[ind, val]
	elif val < 0:
		return None
	elif val == 0:
		return []
	elif ind == -1:
		return None
	elif not vis_arr[ind]:
		ret1 = ret_res(arr, vis_arr, ind - 1, memo, val - arr[ind])
		if ret1 != None:
			ret1.append(ind)
			memo[ind, val] = ret1
			return memo[ind, val]
		ret2 = ret_res(arr, vis_arr, ind - 1, memo, val)
		memo[ind, val] = ret2
		return memo[ind, val]
	else:
		ret3 = ret_res(arr, vis_arr, ind - 1, memo, val)
		memo[ind, val] = ret3
		return memo[ind, val]
for i in range(int(input())):
	(n, k) = map(int, input().split())
	arr = sorted(list(map(int, input().split())))
	tot = sum(arr)
	if tot % k == 0 and k <= n:
		val = tot // k
		vis_arr = [False for _ in range(n)]
		for i in range(k):
			path = ret_res(arr, vis_arr, n - 1, {}, val)
			if path == None:
				print('no')
				break
			else:
				for j in path:
					vis_arr[j] = True
		else:
			print('yes')
	else:
		print('no')


import sys
tests = int(input())
for t in range(tests):
	line = input().split()
	sanskars = int(line[0])
	followers = int(line[1])
	intensities = list(map(int, input().split()))
	ti = sum(intensities)
	togive = ti / followers
	go = 1
	if followers > sanskars or round(togive) != togive or max(intensities) > togive:
		print('no')
		go = 0
	if go == 1:
		intensities.sort(reverse=True)

		def give(intensities, runsum, pos):
			if intensities == [] or intensities[0] == 0:
				return 1
			runsum = (runsum + intensities[pos]) % togive
			intensities.pop(pos)
			if runsum == 0:
				return give(intensities, 0, 0)
			p = pos
			for i in intensities[pos:]:
				if runsum + i <= togive:
					topass = intensities[:]
					if give(topass, runsum, p) == 1:
						return 1
				p += 1
			return 0
		print('yes') if give(intensities, 0, 0) == 1 else print('no')