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.