Блог пользователя DaviddeGea1

Number of ways of dividing an array into 2 parts such that sum of each part is > k
Автор DaviddeGea1, история, 4 года назад, По-английски

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}

  • Проголосовать: нравится
  • +8
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится +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)$$$.

→ Ответить
»
4 года назад, # |
  Проголосовать: нравится +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 $$$.

→ Ответить
»
4 года назад, # |
  Проголосовать: нравится -13 Проголосовать: не нравится

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)
→ Ответить
»
7 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    7 месяцев назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится

    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.

    → Ответить