DaviddeGea1's blog

By DaviddeGea1, history, 7 months ago, In English,

I got this problem in an off-campus round, someone please help me solve the problem:

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}

 
 
 
 
  • Vote: I like it
  • +8
  • Vote: I do not like it

»
7 months ago, # |
  Vote: I like it +3 Vote: I do not like it

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, # |
  Vote: I like it +3 Vote: I do not like it

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   Vote: I like it 0 Vote: I do not like it

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<n;i++)
{
    cin>>array[i];
}
cout <<max(0,int(pow(2,n))-2*(countSubarrays(array, n, k)+1));

}