Problematic Problem This is the Contest Link of Hackerrank which has one question in it named as Bob’s Date. Pls help me by solving this question, I wrote a DP solution but it is failing on some TestCases Can someone pls solve it or give hints for the same.
3 Likes
Isn’t it a trivial knapsack dp problem ?
No It’s not we have to also add minimum weight to it and that also must be distributed equally. I wrote knapsack version only but it’s failing.
I think it can be solved by a knapsack dp, allow me some time I’ll get back to you.
Okk Thanks a lot
For each value V from 0 to 10000, we will traverse and consider it as the weight that should be added on both ends. Now we have to find if there is a way to find two sets S1 and S2 from the input array such that Sum(S1) = Sum(S2) = V and S1, S2 are disjoint. We can do this by knapsack dp i.e. first try to find one subset that sums up to V. From the remaining elements try to get another subset that sums up to V. I think considering any two subsets will work fine. I don’t know if this is correct or not.
UPD: I guess this is not a correct approach.
Wont the time complexity be an issue here for each value of V we running two knapsack dp each with a time complexity of O(n*V).
So, overall time complexity would became something like O(nVV) which would easily timeout i guess.
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