DaviddeGea1's blog

Number of ways of dividing an array into 2 parts such that sum of each part is > k
By DaviddeGea1, history, 5 years 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

Comments Comments (7)
| Write comment?
»
5 years 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)$$$.

→ Reply
»
5 years 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 $$$.

→ Reply
»
4 years ago, # |
  Vote: I like it -13 Vote: I do not like it

Below is the function:

def solve(l,k):
	n = len(l)
	dp = [0]*(k+1)
	s = sum(l)
	dp[0] = 1
	for i in range(n):
		for j in range(k,l[i]-1,-1):
			dp[j] += dp[j-l[i]]
	return 2**n - 2*sum(dp)
→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it -21 Vote: I do not like it

    BUT PLEASE DON'T CHEAT IN PLACEMENT EXAMS.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Wow cheating. This question was asked 9 months ago. Really cool! I've never seen an exam running for 9 months straight.

      → Reply
»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hey, the constraints seem too tight for an O(NK) solution to pass. Anyone has a faster approach?

→ Reply
  • »
    »
    15 months ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    O(NK) is enough to pass, 10^8 operations usually equates to about 1 second of runtime. When the operations are simple, which is the case with dps usually it's usually much less.

    → Reply