### DaviddeGea1's blog

By DaviddeGea1, history, 7 months ago, ,

You are given N elements, each having unique values. If you distribute them among 2 children in such a way that the total unique value that each child receives must be greater than K. How many ways can you distribute the elements so that the mentioned condition holds true?

Since the answer can be very large print it modulo 1e9+7.

1 <= N <= 10^3

1 <= K <= 10^5

1 <= A[i] <= 10^9

Sample Input:

3 5

3 7 4

Sample Output:

2 -> {3,4},{7} and {7},{3,4}

• +8

 » 7 months ago, # |   +3 I think this should work.Let $y$ be the number of subsets of $A$ with sum at most $K$. You can compute this by $dp_{i,j} =$ number of subsets of $0..i$ with sum equal to $j$ in $O(NK)$.Then the solution is $max(0, 2^N - 2y)$.
 » 7 months ago, # |   +3 I'm assuming we can't skip any element from both sets. Then, we know that each person should get at least total of $K+1$. So, the sum of the array should be $\ge 2 \cdot (K+1)$. If not, the answer is 0.If it's possible, then we need to count the number of subsets of the given array having sum $\le K$. Let it be $X$. Then the answer is $2^{n}-2 \cdot X$. We can count the number of subsets having sum $\le K$ using $O( N \cdot K )$ time and $O(K)$ space using DP. $dp[i][j] = dp[i-1][j] + dp[i-1][j-A[i]]$, $1 \le i \le n$ , $0 \le j \le K$.
 » 2 months ago, # | ← Rev. 3 →   0 this is the answer (cpp) :-int countSubarrays(int arr[], int n, int k) { int start = 0, end = 0, count = 0, sum = arr[0]; while (start < n && end < n) { if (sum < k) { end++; if (end >= start) count += end - start; if (end < n) sum += arr[end]; } else { sum -= arr[start]; start++; } } return count; } int main() { `int n,k; cin>>n>>k; int *array= new int[n]; for(int i=0;i>array[i]; } cout <