# 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

Subtask #2 (70 points): original constraints

```1
4 2
1 2 3 4
```

```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.

Sharing Is Caring