Chef and Interesting Subsequences Codechef Solution

Chef and Interesting Subsequences Codechef Solution: Chef has a sequence A1,A2,…,ANA1,A2,…,AN. This sequence has exactly 2N2N subsequences. Chef considers a subsequence of AA interesting if its size is exactly KK and the sum of all its elements is minimum possible, i.e. there is no subsequence with size KK which has a smaller sum.

Help Chef find the number of interesting subsequences of the sequence AA.

Input

  • The first line of the input contains a single integer TT denoting the number of test cases. The description of TT test cases follows.
  • The first line of each test case contains two space-separated integers NN and KK.
  • The second line contains NN space-separated integers A1,A2,…,ANA1,A2,…,AN.

Output

For each test case, print a single line containing one integer ― the number of interesting subsequences.

Constraints

  • 1≤T≤101≤T≤10
  • 1≤K≤N≤501≤K≤N≤50
  • 1≤Ai≤1001≤Ai≤100 for each valid ii

Subtasks

Subtask #1 (30 points): 1≤N≤201≤N≤20

Subtask #2 (70 points): original constraints

Sample Input 1 

1
4 2
1 2 3 4

Sample Output 1 

1

Explanation

Example case 1: There are six subsequences with length 22: (1,2)(1,2), (1,3)(1,3), (1,4)(1,4), (2,3)(2,3), (2,4)(2,4) and (3,4)(3,4). The minimum sum is 33 and the only subsequence with this sum is (1,2)(1,2).

Chef and Interesting Subsequences- CodeChef Solution in JAVA

import java.util.*;
class HelloWorld {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int T = in.nextInt();
		while(T-- > 0) {
			int N = in.nextInt();
			int K = in.nextInt();
			int[] arr = new int[N];
			Map<Integer, Integer> map = new HashMap<>();
			for(int i=0; i<N; i++) {
				arr[i] = in.nextInt();
				map.put(arr[i], map.getOrDefault(arr[i], 0) + 1);
			}
			Arrays.sort(arr);
			int m = arr[K-1];
			int n = 1;
			for(int i=K-2; i>=0 && arr[i] == m; i--) n++;
			long count = binomialCoeff(map.get(m), n);
			System.out.println(count);
		}
	}
	static long binomialCoeff(int n, int k)
    {
        long C[][] = new long[n + 1][k + 1];
        int i, j;
        for (i = 0; i <= n; i++) {
            for (j = 0; j <= Math.min(i, k); j++) {
                // Base Cases
                if (j == 0 || j == i)
                    C[i][j] = 1;
                else
                    C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
            }
        }
        return C[n][k];
    }
}

Chef and Interesting Subsequences – CodeChef Solution in CPP

#include<bits/stdc++.h>
using namespace std;
long long C(long n, long r) {
	long long p = 1, k = 1;
	if (n - r < r) r = n - r;
	if (n != 0) {
		while(r > 0) {
			p = p * n;
			k = k * r;
			long long m = __gcd(p,k);
			p = p / m;
			k = k / m;
			n--;
			r--;
		}
	}else p = 1;
	return p;
}
int main() {
	long t;
	cin >> t;
	for (long x = 0; x < t; x++) {
		long n,k;
		cin >> n >> k;
		long long a[n];
		for (long j = 0; j < n; j++) {
			cin >> a[j];
		}
		sort(a,a+n);
		long long mx = 0;
		for (long i = 0; i < k; i++) {
			mx = max(mx,a[i]);
		}
		long long slm = 0;
		for (long j = 0; j < n; j++) {
			if (a[j] == mx) slm++;
		}
		long long sm = 0;
		for (long i = 0; i < k; i++) {
			if (a[i] == mx) sm++;
		}
		cout << C(slm,sm) << endl;
	}
	return 0;
}

Chef and Interesting Subsequences-CodeChef Solution in Python

t = int(input())
for i in range(t):
    n, k = map(int, input().split())
    l = sorted(list(map(int, input().split())))
    x = l.count(l[k - 1])
    y = l[:k].count(l[k - 1])
    a = 1
    b = 1
    for j in range(x - y + 1, x + 1):
        a *= j
    for z in range(1, y + 1):
        b *= z
    print(a // b)

Disclaimer: The above Problem(Chef and Interesting Subsequences) is generated by CodeChef but the solution is provided by  Chase2learn.This tutorial is only for Educational and Learning purpose.

Leave a Comment