Physical Address
304 North Cardinal St.
Dorchester Center, MA 02124
Alok-nath and His Sanskars CodeChef Solution
Problem -Alok-nath and His Sanskars CodeChef Solution
This website is dedicated for CodeChef solution where we will publish right solution of all your favourite CodeChef problems along with detailed explanatory of different competitive programming concepts and languages.
Alok-nath and His Sanskars CodeChef Solution in C++14
#include<bits/stdc++.h>
#include<cstring>
using namespace std;
typedef long long int ll;
typedef vector<long long int> vll;
typedef vector<int> vi;
typedef pair<long long int, long long int> pll;
typedef pair<int, int> pi;
// constraints n<100 W<1000
ll t[100][1002];
// int minDiff = INT_MAX;
bool backtrack(vll& nums, vector<bool>& used, ll tsum, ll currsum, int k, int index) {
if (k == 1) {
return true;
}
if (currsum == tsum) {
return backtrack(nums, used, tsum, 0, k - 1, 0);
}
for (int i = index; i < nums.size(); i++) {
if (used[i] || (currsum + nums[i]) > tsum) {
continue;
}
used[i] = true;
if (backtrack(nums, used, tsum, currsum + nums[i], k, i + 1)) {
return true;
}
used[i] = false;
if (currsum == 0) {
break;
}
}
return false;
}
bool canPartitionKSubsets(vll& nums, int k) {
ll sum = 0;
int n = nums.size();
for (int i = 0; i < n; i++) {
sum += nums[i];
}
if (k>n || sum % k != 0) {
return false;
}
ll tsum = sum / k, currsum = 0;
vector<bool> used(n, false);
sort(nums.begin(), nums.end(), greater<int>());
if (nums[0] > tsum) {
return false;
}
return backtrack(nums, used, tsum, currsum, k, 0);
}
void solve() {
ll n, k;
memset(t, -1, sizeof(t));
cin >> n >> k;
vll arr(n);
ll sum = 0;
for (ll i = 0; i < n; i++) {
cin >> arr[i];
}
if(canPartitionKSubsets(arr, k)){
cout<<"yes";
}
else cout<<"no";
cout<<"\n";
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
ll t;
cin >> t;
while (t--) {
solve();
}
return 0;
}Alok-nath and His Sanskars CodeChef Solution in PYTH 3
# cook your dish here
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)
#assume sum of A is divisible by K and equals SSUM
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
#Y=[[False]*N]*SSUM
if(hasPartition(A,SSUM,K)):
print('yes')
else:
print('no')
Alok-nath and His Sanskars CodeChef Solution in C
#include<stdio.h>
int isSubsetSum(long long *a,int n,int m)
{
if(m==0)
return 1;
if(n==0)
return 0;
if(a[n-1]>m||a[n-1]<0)
return isSubsetSum(a,n-1,m);
if(isSubsetSum(a,n-1,m-a[n-1]))
{
a[n-1]=-1;
return 1;
}
return isSubsetSum(a,n-1,m);
}
int main()
{
int i,t,n,m,cnt,flag;
long long sum,a[22],x;
scanf("%d",&t);
while(t--)
{
sum=0;cnt=0;flag=0;
scanf("%d%d",&n,&m);
for(i=0;i<n;i++)
{
scanf("%lld",&a[i]);
sum+=a[i];
}
if(n<m)
flag=0;
else if(sum%m==0)
{
x=sum/m;
for(i=0;i<m;i++)
{
if(isSubsetSum(a,n,x))
{
cnt++;
}
else
{
break;
}
}
if(cnt==m)
flag=1;
else
flag=0;
}
else
{
flag=0;
}
if(flag)
printf("yes\n");
else
printf("no\n");
}
return 0;
}
/* 1541256279063 */Alok-nath and His Sanskars CodeChef Solution in JAVA
import java.util.*;
class Main
{
public static void main (String[] args) throws java.lang.Exception
{
Scanner scanner = new Scanner(System.in);
int testcases = scanner.nextInt();
for(int t =0; t <testcases; t++){
Long sum = 0L;
int n = scanner.nextInt();
int k = scanner.nextInt();
//sankars
Long[] arr = new Long[n];
for(int i = 0; i<n; i++){
arr[i] = scanner.nextLong();
sum += arr[i];
}
//corners
if(k>n){
System.out.println("no");
continue;
}
if(sum%k!=0){
System.out.println("no");
continue;
}
//k shares
Long share = sum / Long.parseLong(k + "");
int ans = 1;
for(int i=0; i<k; i++){
if(!cal(arr, n-1, share)){
ans = 0;
break;
}
}
System.out.println((ans == 1) ? "yes" : "no");
}
scanner.close();
}
public static boolean cal(Long[] arr, int i, Long sum){
if(sum == 0) return true;
if(i < 0) return false;
Long val = arr[i];
if(val <= sum){
arr[i] = 0L;
boolean isBalanced = cal(arr, i-1, sum-val);
if(isBalanced) return true;
arr[i] = val;
return cal(arr, i-1, sum);
}
else{
return cal(arr, i-1, sum);
}
}
}Alok-nath and His Sanskars CodeChef Solution in PYPY 3
import sys
import math
sys.setrecursionlimit(10**6)
def isKPartitionPossibleRec(arr, subsetSum, taken,
subset, K, N, curIdx, limitIdx):
if subsetSum[curIdx] == subset:
""" current index (K - 2) represents (K - 1)
subsets of equal sum last partition will
already remain with sum 'subset'"""
if (curIdx == K - 2):
return True
# recursive call for next subsetition
return isKPartitionPossibleRec(arr, subsetSum, taken,
subset, K, N, curIdx + 1 , N - 1)
# start from limitIdx and include
# elements into current partition
for i in range(limitIdx, -1, -1):
# if already taken, continue
if (taken[i]):
continue
tmp = subsetSum[curIdx] + arr[i]
# if temp is less than subset, then only
# include the element and call recursively
if (tmp <= subset):
# mark the element and include into
# current partition sum
taken[i] = True
subsetSum[curIdx] += arr[i]
nxt = isKPartitionPossibleRec(arr, subsetSum, taken,
subset, K, N, curIdx, i - 1)
# after recursive call unmark the element and
# remove from subsetition sum
taken[i] = False
subsetSum[curIdx] -= arr[i]
if (nxt):
return True
return False
# Method returns True if arr can be
# partitioned into K subsets with equal sum
def isKPartitionPossible(arr, N, K):
# If K is 1,
# then complete array will be our answer
if (K == 1):
return True
# If total number of partitions are more than N,
# then division is not possible
if (N < K):
return False
# if array sum is not divisible by K then
# we can't divide array into K partitions
sum = 0
for i in range(N):
sum += arr[i]
if (sum % K != 0):
return False
# the sum of each subset should be subset (= sum / K)
subset = sum // K
subsetSum = [0] * K
taken = [0] * N
# Initialize sum of each subset from 0
for i in range(K):
subsetSum[i] = 0
# mark all elements as not taken
for i in range(N):
taken[i] = False
# initialize first subsubset sum as
# last element of array and mark that as taken
subsetSum[0] = arr[N - 1]
taken[N - 1] = True
# call recursive method to check
# K-substitution condition
return isKPartitionPossibleRec(arr, subsetSum, taken,
subset, K, N, 0, N - 1)
try:
T = int(input())
for l in range(T):
n,k = [int(i) for i in input().strip().split(" ")]
path = [int(i) for i in input().strip().split(" ")]
if isKPartitionPossible(path,n,k):
print("yes")
else:
print("no")
except EOFError:
pass
Alok-nath and His Sanskars CodeChef Solution in PYTH
def donext(cv,V,K,B,p,N):
if D[0] == 0:
for i in range(p,N):
if (B[i] == 0) and (A[i]+cv <= V):
NB = list(B)
NB[i] = 1
if A[i]+cv == V:
if K == 1:
D[0] = 1
else:
k = 0
while NB[k] == 1:
k += 1
# endwhile
NB[k] = 1
donext(A[k],V,K-1,NB,k+1,N)
# endif
else:
donext(A[i]+cv,V,K,NB,i+1,N)
# endif
# endif
# endfor i
# endif
# end fun
t = int(raw_input())
for i in range(t):
st = raw_input().split()
N = int(st[0])
K = int(st[1])
st = raw_input().split()
A = []
tot = 0
for x in st:
n = int(x)
A.append(n)
tot += n
# endfor x
A.sort()
A.reverse()
V = tot/K
if (tot%K > 0) or (A[0] > V) or ((tot == 0) and (N < K)):
r = 0
else:
if K == 1:
r = 1
else:
while (N > 0) and (A[0] == V):
N -= 1
K -= 1
del(A[0])
# endwhile
if K < 2:
r = 1
else:
B = [0 for x in range(N)]
B[0] = 1
K -= 1
D = [0]
donext(A[0],V,K,B,1,N)
r = D[0]
# endif
# endif
# endif
if r == 0:
print 'no'
else:
print 'yes'
# endif
# endfor i
Alok-nath and His Sanskars CodeChef Solution in C#
using System;
using System.Linq;
class GFG
{
static bool issubsetsum(long[] a, long n, long sum)
{
if (sum == 0)
return true;
if (n == 0)
return false;
if (a[n - 1] > sum || a[n - 1] < 0)
return issubsetsum(a, n - 1, sum);
if (issubsetsum(a, n - 1, sum - a[n - 1]))
{
a[n - 1] = -1;
return true;
}
return issubsetsum(a, n - 1, sum);
}
// Driver Code
public static void Main()
{
var t = int.Parse(Console.ReadLine());
for (int f = 0; f < t; f++)
{
string[] input1 = Console.ReadLine().Split(' ');
var n = int.Parse(input1[0]);
var k = int.Parse(input1[1]);
string[] input2 = Console.ReadLine().Split(' ');
long[] arr = new long[n];
for (int i = 0; i < input2.Length; i++)
{
if (!string.IsNullOrEmpty(input2[i]))
arr[i] = int.Parse(input2[i]);
}
var ans = canPartitionKSubsets(arr, k, n) == true ? "yes" : "no";
Console.Write(ans);
Console.WriteLine();
}
}
private static bool canPartitionKSubsets(long[] arr, long k, long n)
{
var sum = arr.Sum();
if (sum % k != 0 || n < k)
{
return false;
}
int count = 0;
long p = sum / k;
for (int i = 0; i < k; i++)
{
if (issubsetsum(arr, n, p))
count++;
else break;
}
if (count == k)
return true;
return false;
}
}Alok-nath and His Sanskars CodeChef Solution Review:
In our experience, we suggest you solve this Alok-nath and His Sanskars CodeChef Solution and gain some new skills from Professionals completely free and we assure you will be worth it.
If you are stuck anywhere between any coding problem, just visit Queslers to get the Alok-nath and His Sanskars CodeChef Solution.
Conclusion:
I hope this Alok-nath and His Sanskars CodeChef Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.
This Problem is intended for audiences of all experiences who are interested in learning about Programming Language in a business context; there are no prerequisites.
Keep Learning!
