CHEFINSQ - Editorial

PROBLEM LINKS :

Contest : Division 1

Contest : Division 2

Practice

Setter : Aman Gupta

Tester : Istvan Nagy

Editorialist : Anand Jaisingh

DIFFICULTY :

Easy

PREREQUISITES :

Ad-Hoc logic, Binomial Coefficients.

PROBLEM :

Given an array A of size N, you need to find the number of sub sequences of this array of length K, such that the sum of these sub sequences is the minimum possible sum of a sub sequence of length K

QUICK EXPLANATION :

It can be proved that the minimum possible sum of a subsequence of length K from the given array A[] is the sum of the K smallest elements of array A[]. Let the maximum element among the K smallest elements of the array be Z , and let the number of times it occurs among the K smallest elements of the array be Y. Also, let cnt(i) indicate the number of times element i occurs in the given array. Then, we can additionally prove that the answer equals \binom{cnt(Z)}{Y}

EXPLANATION :

Claim :

The minimum possible sum of a subsequence of length K from the given array A of size N is the sum of the K smallest elements of the array.

Proof :

Let’s call the minimum possible sum of a subsequence of length K as Sum and let initially let Sum be equal to the sum of the K smallest elements of the array. Now, let’s try and pick some integer Y not included among the K smallest elements. Now, we try and replace some element X included among the K smallest elements.

In such a situation, Sum transforms to Sum+Y-X. But, since we know that Y \ge X , then Y-X \ge 0 . Hence, it’s never optimal to pick any element outside of the K smallest elements of the array, since in such a case, Sum can only possibly increase.

Claim :

Let the maximum element among the K smallest elements of the array be Z , and let the number of times it occurs among the K smallest elements of the array be Y. Also, let cnt(i) indicate the number of times element i occurs in the given array. Then the answer is \binom{cnt(Z)}{Y}

Proof :

First, let’s imagine we remove all elements \ge Z from the array. Then, the number of elements we will be left with will be M < K . It’s easy to see since we remove at least all elements with position \ge K (After sorting )

Now, we need to make M equal to K. In order to do that we need to keep on adding Z to the array. We obviously cannot add any element > Z . But since Z occurs a total of cnt(i) times in the given array and K-M=Y, so we can still make a subsequence with the same possible sum in \binom{cnt(Z)}{Y} different ways.

Now, the factorial way of computing binomial coefficients may be too much here, i.e. \binom{N}{R}=\frac{N!}{R! \cdot (N-R)!} N! can be too large to fit into any primitive data types. But remember, after division, \binom{N}{R} is good enough to fit into a long long integer. So instead, we can use the recurrence :

C(i,j)=C(i-1,j-1)+C(i-1,j)

This is the way of computing Pascal’s Triangle, and you can read further about it here.

That’ it, Thank you !

Your Comments are Welcome !

COMPLEXITY ANALYSIS :

Time Complexity : O( (MaxN)^2+ T \cdot N \lg N ) , where MaxN \approx 50

Space Complexity: O((MaxN)^2)

SOLUTION LINKS :

Setter
#include <bits/stdc++.h>
 
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)
 
template<class T> bool umin(T &a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool umax(T &a, T b) { return a < b ? (a = b, true) : false; }
 
using namespace std;
 
long long readInt(long long l, long long r, char endd) {
	long long x = 0;
	int cnt = 0;
	int fi = -1;
	bool is_neg = false;
	while (true) {
		char g = getchar();
		if (g == '-') {
			assert(fi == -1);
			is_neg = true;
			continue;
		}
		if ('0' <= g && g <= '9') {
			x *= 10;
			x += g - '0';
			if (cnt == 0) {
				fi = g - '0';
			}
			cnt++;
			assert(fi != 0 || cnt == 1);
			assert(fi != 0 || is_neg == false);
 
			assert(!(cnt > 19 || (cnt == 19 && fi > 1)));
		}
		else if (g == endd) {
			assert(cnt > 0);
			if (is_neg) {
				x = -x;
			}
			assert(l <= x && x <= r);
			return x;
		}
		else {
			assert(false);
		}
	}
}
 
string readString(int l, int r, char endd) {
	string ret = "";
	int cnt = 0;
	while (true) {
		char g = getchar();
		assert(g != -1);
		if (g == endd) {
			break;
		}
		cnt++;
		ret += g;
	}
	assert(l <= cnt && cnt <= r);
	return ret;
}
long long readIntSp(long long l, long long r) {
	return readInt(l, r, ' ');
}
long long readIntLn(long long l, long long r) {
	return readInt(l, r, '\n');
}
string readStringLn(int l, int r) {
	return readString(l, r, '\n');
}
string readStringSp(int l, int r) {
	return readString(l, r, ' ');
}
 
int main(int argc, char** argv)
{
#ifdef HOME
	if (IsDebuggerPresent())
	{
		freopen("../in.txt", "rb", stdin);
		freopen("../out.txt", "wb", stdout);
	}
#endif
	int T, K, N;
 
	vector< vector<int64_t> > binom(60, vector<int64_t>(64));
	binom[0][0] = 1;
	for (int i = 1; i < 60; ++i)
	{
		binom[i][0] = 1;
		for (int j = 1; j < 60; ++j)
		{
			binom[i][j] = binom[i - 1][j - 1] + binom[i - 1][j];
		}
	}
	T = readIntLn(1, 10);
	for (int tc = 0; tc < T; ++tc)
	{
		N = readIntSp(1, 50);
		K = readIntLn(1, N);
		vector<int> A(N);
		for (int i = 0; i < N; ++i)
		{
			if(i + 1 < N)
				A[i] = readIntSp(1, 100);
			else
				A[i] = readIntLn(1, 100);
		}
		//assert(getchar() == -1);
		sort(A.begin(), A.end());
 
		int Z = A[K - 1];
		int cnt = 0, lcnt = 0;
		for (int i = 0; i < N; ++i)
		{
			if (i < K && A[i] == Z)
				++lcnt;
			if (A[i] == Z)
				++cnt;
		}
		printf("%lld\n", binom[cnt][lcnt]);
	}
	assert(getchar() == -1);
	return 0;
}   
Tester
#include <bits/stdc++.h>
 
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)
 
template<class T> bool umin(T &a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool umax(T &a, T b) { return a < b ? (a = b, true) : false; }
 
using namespace std;
 
int main(int argc, char** argv)
{
#ifdef HOME
	if (IsDebuggerPresent())
	{
		freopen("../in.txt", "rb", stdin);
		freopen("../out.txt", "wb", stdout);
	}
#endif
	int T, K, N;
	
	vector< vector<int64_t> > binom(60, vector<int64_t>(64));
	binom[0][0] = 1;
	for (int i = 1; i < 60; ++i)
	{
		binom[i][0] = 1;
		for (int j = 1; j < 60; ++j)
		{
			binom[i][j] = binom[i - 1][j - 1] + binom[i - 1][j];
		}
	}
 
	scanf("%d", &T);
	for (int tc = 0; tc < T; ++tc)
	{
		scanf("%d %d", &N, &K);
		vector<int> A(N);
		for(int i = 0; i < N; ++i)
			scanf("%d", &A[i]);
		sort(A.begin(), A.end());
 
		int Z = A[K - 1];
		int cnt = 0, lcnt = 0;
		for (int i = 0; i < N; ++i)
		{
			if (i < K && A[i] == Z)
				++lcnt;
			if (A[i] == Z)
				++cnt;
		}
		printf("%lld\n", binom[cnt][lcnt]);
	}
	return 0;
}
Editorialist
//#pragma GCC optimize("Ofast,no-stack-protector")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx")
//#pragma GCC target("avx,tune=native")
// Anand Jaisingh

#include<bits/stdc++.h>

using namespace std;

typedef complex<double> base;
typedef long double ld;
typedef long long ll;

#define pb push_back
#define pii pair<int,int>
#define pll pair< ll , ll >
#define vi vector<int>
#define vvi vector< vi >
const int maxn=(int)(2e5+5);
const ll mod=(ll)(1e9+7);
int a[maxn];
ll dp[55][55];

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);

    int t;cin>>t;

    dp[0][0]=1;

    for(int i=1;i<51;i++)
    {
        dp[i][0]=1;

        for(int j=1;j<51;j++)
        {
            dp[i][j]=dp[i-1][j]+dp[i-1][j-1];
        }
    }

    while(t>0)
    {
        int n,k;

        cin>>n>>k;map<int,int> m1;

        for(int i=0;i<n;i++)
        {
            cin>>a[i];

            m1[a[i]]++;
        }

        sort(a,a+n);

        int ptr=k-1,val=0;

        while(ptr>=0 && a[ptr]==a[k-1])
        {
            ptr--;val++;
        }

        ll res=dp[m1[a[k-1]]][val];

        cout<<res<<endl;

        t--;
    }

    return 0;
}
5 Likes

Out of the 7 subtasks …6 have passed successfully. But 1 is not passing…I guess it is because of worst case scenario where my algorithm has to calculate factorial(50)…
Please tell me what to do for that

#include <bits/stdc++.h>
using namespace std;
#define ll long long

ll fac(ll n,ll r)
{
ll i,f=1;
for(i=n;i>r;i–)
{
f*=i;
}
return f;
}

ll fact(ll n,ll r)
{
ll m,f1,f2,m1;
m=r>n-r?r:n-r;
m1=r<n-r?r:n-r;
f1=fac(n,m);
f2=fac(m1,1);
return f1/f2;
}

int main()
{
int t,c,c1,c2,ch,i,n,k;
cin>>t;
while(t–)
{
cin>>n>>k;
int a[n];
for(i=0;i<n;i++)
{
cin>>a[i];
}
sort(a,a+n);
c=a[k-1];
c1=0;
ch=0;
for(i=0;i<n;i++)
{

        if(a[i]==c){c1++;
            if(ch==0)c2=i;
            ch=1;
        }
    }
    cout<<fact(c1,k-c2)<<endl;
}
return 0;

}

Just build a lookup table, using the well-known recurrence relation for nCr :slight_smile:

https://www.codechef.com/viewsolution/26609992

6 Likes

In my solution I had used partial_sort till the first K elements instead of sorting the entire array and computed C (n, r) in linear time to get an overall complexity of O(T \cdot N \lg N). Got 0.00 secs runtime.

#include <iostream>
#include <algorithm>

using namespace std;

int main ()
{
    ios :: sync_with_stdio (false);
    cin.tie (NULL);
    cout.tie (NULL);

    int T;
    cin >> T;

    while (T--)
    {
        int n, k;
        cin >> n >> k;

        int a[n];
        for (int i = 0; i < n; ++i)
            cin >> a[i];
        
        partial_sort (a, a + k, a + n);

        int l = 1;
        for (int i = k - 1; i > 0 && a[i] == a[i - 1]; --i, ++l);

        int r = 0;
        for (int i = k; i < n; ++i)
            if (a[i] == a[k - 1])
                ++r;
        
        int N = l + r;
        int R = l < r ? l : r;

        unsigned long long result = 1;
        for (int i = 1; i <= R; ++i)
            result = result * (i + N - R) / i;

        cout << result << "\n";
    }

    return 0;
}
3 Likes

Well if you insist on using this approach, since the constraints are small you can use arrays to compute the factorials or you could use a manual “BigInt” implementation (comes in handy) . This one seems to be feasible for the purpose: https://codeforces.com/blog/entry/16380
AC Solution using the same

1 Like

It’s not recommended to do it that way, though for the given constraints it works.

In case of n = 50 and r = 25 , you are calculating 50 * 49 * 48 * …*25 and this value is big for even long long int and so you are getting WA because of garbage value.
So here is my implementation of Combination function

Summary

long long nCr(int a, int b){
long long ans1[51] , ans2[51] ,ans3 = 1, ans4 = 1 ;
long long m = max(a-b,b);
long long n = min(a-b,b);
for(int i = a ; i > m ; i–) ans1[i] = i;
for(int j = 1 ; j <= n ; j++) ans2[j] = j;
for(int i = a ; i > m ; i–){
for(int j = n ; j > 1 ; j–){
{
for(int k = 2 ; k <= 50 ; k++){
if(ans1[i] % k == 0 && ans2[j] % k == 0){
ans1[i] = ans1[i]/k;
ans2[j] = ans2[j]/k;
}
}
}
}
}
for(int i = a ; i > m ; i–) ans3 *= ans1[i];
for(int j = 1 ; j <= n ; j++) ans4 *= ans2[j];
return(ans3/ans4);
}

Well written, beautiful code, this inspired me.

1 Like

Only 1 subtask failed on second list, which case might be failing for my code using DP ?

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

class Codechef {

public static void main(String[] args) throws IOException{
   class ValueCountPair
   {
		int val;
		int count;
		public ValueCountPair(int val, int count) {
			this.val = val;
			this.count = count;
		}
		
		public void setCount(int count) {
			this.count = count;
		}
		
		public int getCount() {
			return count;
		}
		
		public int getVal() {
			return val;
		}
	}
	
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	int t = Integer.parseInt(br.readLine());
	
	while(t-- != 0)
	{
		String str[] = br.readLine().trim().split("\\s+");
		int n = Integer.parseInt(str[0]);
		int k = Integer.parseInt(str[1]);
		
		String strs[] = br.readLine().trim().split("\\s+");
		ValueCountPair cache[][] = new ValueCountPair[k+1][n+1];
		int i, j;
		
		for(i=0;i<=n;i++)
			cache[0][i] = new ValueCountPair(0, 0);
		
		for(i=1;i<=k;i++)
		{				
			for(j=i;j<=n;j++)
			{
				if(i==j)				
					cache[i][j] = new ValueCountPair(Integer.parseInt(strs[j-1])+cache[i-1][j-1].getVal(), 1);				
				else
				{
					int newVal =  Integer.parseInt(strs[j-1])+cache[i-1][j-1].getVal();
					
					if(cache[i][j-1].getVal() == newVal)
					{						
						if(i==1) // 4 2     2 2 2 2
						{							
							cache[i][j] = new ValueCountPair(newVal, cache[i][j-1].getCount() + 1);
						}						
						else
						{
							cache[i][j] = new ValueCountPair(cache[i][j-1].getVal(),cache[i][j-1].getCount());
							cache[i][j].setCount(cache[i][j-1].getCount() + cache[i-1][j-1].getCount());	
						}						
					}
					else if(cache[i][j-1].getVal() > newVal)
					{						
						if(i!=1) // 5 4     2 3 2 3 2
							cache[i][j] = new ValueCountPair(newVal, cache[i-1][j-1].getCount());
						else
							cache[i][j] = new ValueCountPair(newVal, 1);
					}
					else
					{
						cache[i][j] = new ValueCountPair(cache[i][j-1].getVal(),cache[i][j-1].getCount());
					}
				}
			}
		}			
		System.out.println(cache[k][n].getCount());			
	}
}

}

Consider e.g.

1
10 45
2 3 2 11 5 10 14 9 10 1 

Hi guys, if you’ll are pasting code in the comments, I suggest to use a hide detail to post it, for example, “[details=“Code”] Your code [/details]”, it will look much better and make the comments section easier to read

5 Likes

k > n, so we can’t form any set with k many elements and so the output should be 0 right?:thinking:

That’s right :slight_smile: blah 20 characters blah

1 Like

But in problem it is given that k<=n right ?? How is K>n even possible in input ?

1 Like

Where does it say that?

In the constraints only, it is given right ?

Whoops - yes, you’re right - didn’t see that there :slight_smile:

1 Like

@ssjgz When can we expect to see your editorial style documentation for FUZZYLIN? I really want to go through your explanation. :slightly_smiling_face:

Oops - completely forgot about that :confused:

I’ve got quite a lot going on IRL at the moment, so it might have to wait until after the weekend.

It won’t be any better than the official Editorial explanation though, I don’t think.

1 Like

No problem. :blush:
I’d still love to take a look at your editorial. Take your time. I just wanted to make sure that it’s coming. Thank you once again for the other editorials too! Cheers! :+1:

1 Like