O(n Vsquare)
The question doesn’t clarify whether we have to give a configuration with a weight of at least W or a configuration with the least weight greater than W
I think we have to find the min weight that should be added on each ends such that the total weight will be greater than or equal to W.
yep this is correct explanation
Did anyone figure it out ? I’m trying the knapsack dp approach to check the minimum equal sum I can obtain where 2*sum+weight_of_rod >= required_weight and printing the elements but still getting only 4 test cases right. Did anyone get more?
I am also getting only 4 test cases passed. I am doing like this -
- If w <= wr, then printing just 0.
- Else, I have created the dp[i][j] = (is j sum possible using the first i values ) ,the normal knapsack dp.
- Now, to check whether two disjoint subsets exists whose sum is equal and more than ceil of (w - wr) / 2, If the sum is possible, then I start to take elements from nth index and check if dp[i-1][j - arr[i]] exists or not. If it that means, there is a subset including this index forming the sum and go on taking the values and marking the indices taken. Now, we again create a dp[i][j] using the values not taken and then check again our sum is possible or not, if possible generate the subset in same way.
The complexity using bitsets becomes (W.W.N) / 32 , which should be enough only.
I think this is correct, but don’t why it is not passing all the cases (giving WA in some).
Jul 19, 2022 - Codeshare
1 Like
@shobhit10058 Try For this test case :
6 19 11
3 2 1 1 1 1 1 6
Your Output :
NO
Correct Ans :
YES
4
1 3 1 1 2
lol, you want to give 8 numbers, but you have given n = 6 only.
It should be
8 19 11
3 2 1 1 1 1 1 6
And my code gives correct output for this.
8 19 11
3 2 1 1 1 1 1 6
YES
4
3 1 1 1 1 1
I don’t have any test case.
But consider three sets S1, S2, S3 where Sum(S1) = Sum(S2) = Sum(S3) = V.
S1 = {a1, a2, a3, a4, a5} , S2 = {a10, a11, a12, a13, a14} , S3 = {a3, a4, a13, a14, a25}.
If we consider S3 as the first set, then i think we can’t find any other disjoint set.
But if we consider S1 or S2 as the first set we can one disjoint set to this.
Not sure if this is correct or am i missing something.
Hm, yes Its correct. I think its hard to find the two subsets like this. But that number(that should be put on both sides) can be found by constucting the dp[i][j][k] = j possible in first and k in other using first i elements.
dp[i][j][k] = dp[i - 1][j - arr[i] ][k] | dp[i - 1][j][k - arr[i] ] | dp[i - 1][j][k]
Using bitsets, again the complexity will be W.W.N / 32 and space W.W / 32. At last just check for which the dp[n][sum][sum] for sum: 0 → 10^4
using this also, we can find the two subsets, but then space will increase much it will become
W.W.N / 32, even in the above also it is at border. But, then also I will put up the construction that I was thinking with this too -
We now know that dp[n][s][s] is possible. then we do following -
Initialise j = s, k = s.
Again, we can start from nth index, then check if dp[n - 1][j - arr[n] ] [k] or dp[n - 1][j][k - arr[n] ] exists or not. If exists, then take the present number and then suitably update j or k depending the which one dp[n - 1][j - arr[n]][k] or dp[n - 1][j ][k - arr[n]] exists and go on taking numbers like this.
@shobhit10058
6 19 11
3 2 1 1 1 1
lol you should also try for 6 size, try both the way n. by mistake I make 2 extra numbers.
Your Output : NO
1 Like
yes that was not correct
I tried a lot but wasn’t able to find a solution that would pass in the given constraints. I think the completely correct solution for the problem is exponential. No one has been able to solve it completely till now.
Please look into the problem @taran_1407
@tehlka Your Code is not passing on this testcase
6 19 11
3 2 1 1 1 1
Your Code Output : NO
Correct Output :
YES
4
1 3 1 1 2
Since all weights can either be on left side, right side or neither, O(3^N) solution is possible.
But we can use DP, specifically f(p, x, y) denotes when considering first p weights, can we achieve x weight on left and y on right side? f(p, x, y) = f(p-1, x, y) || f(p-1, x-A_p, y) || f(p-1, x, y-A_p)
The time complexity of this approach would be O(N*(W/2)^2), roughly 25*10^8 iterations which is too much to pass, but that’s the best I can think right away. Some constant optimizations would be possible too.
Can you please confirm this once?.
I am not coming up with the complexity less than O(NW^2). Anyway first step is to write even a brute solution then we can improve it’s complexity. Give it a try please.