Pls help, you are genius man

help
1

if both configuration of weight given in question are valid then how you will approach the same question
means
e.g:

  • 1 2 2 1 ||Rod Center|| 1 1 1 3 is a right configuration
  • 1 2 3 1 ||Rod Center|| 1 3 2 1 is a right configuration.
1 Like
2

The first one will be a wrong configuration as given in the problem statement. You may have misread it.

3

We will keep on adding the weights until we get the sum greater than equal to W.

4

pls read this first, if both configuration of weight given in question are valid then how you will approach the same question

1 Like
5

No, He is asking “if” the problem is the other way round.
He is changing the problem statement and asking how to solve this.

1 Like
6

It then becomes a variant of the subset sum problem, I guess

7

Oh yes! My bad :slight_smile:

1 Like
8

yep you are right, but how much time complexity your solution will take to solve it

9

we have to add equal amount of weight on both of the side

1 Like
10

As far as I searched online, the time complexity of this variant could be O(Sum \times N), where Sum is the extra weight needed on both sides and N is the number of weights available. This could go very high for some strong test cases and for constraints around 10^5 or 10^6.

2 Likes
11

Oh, I assumed the problem in a different way, not keeping in mind that weights have to be equal on both sides.

12

a/c to my algorithm it will take approx O(sum x n x n) , so I want others suggestion, can we decrease time complexity

13

Is this O(sum * n * n)?
If yes, then this approach will fail even for smaller test cases (constraints around 10^3).

14

yep

15

a/c to you, you can solve it in O(Sum x n), can you pls explain your approach?

16

It was not my approach :sweat_smile:. I browsed some websites regarding such, found that it was a variant of subset problem. I haven’t come up with a solution but just gave a thought that it can be solved by modifying a little bit - which means time complexity wouldn’t change much.

I think @cubefreak777 shall help us with this variant.

1 Like
17

I am thinking that you are saying both left side and right side should have equal total weight.
Then:-
You can approach this question using dynamic programming.
The approach currently coming in my mind is dp[i][wt1][wt2] (bool variable)
it means is it possible upto ith weight that left side have wt1 and right side is wt2.
Now we have three option that

  1. dont put this weight on left and right side :-
    dp[i][j][k] |= dp[i-1][j][k]
  2. put this on left side
    dp[i][j][k] |= dp[i-1][j-wt[i]][k]
  3. put this on right side
    dp[i][j][k] |= dp[i-1][j][k-wt[i]]

Then answer will be for which maximum w dp[n-1] [w ][w] is true.

4 Likes
18

So It’s Complexity is O(N*W*W) ie O(N^3) . Can any reduction of complexity is possible ?
And if we do like First taking max(ceil(required weight/2) , sum of weights/2) and then checking for min required sum if there come ways of diving into 2 subset then that will be the answer, ie first equal partition and then removing the numbers which we take firstly and again check that wether sum is possible . If yes we can otherwise not.
Are mine and yours complexity same ?

1 Like
19

I could not understand your approach but as far as reducing the time complexity is concerned
I think thats not possible ( I may be wrong) because a weight is going to have three sides
so keeping track of two is must .
But one thing can be done that you can take j<=k (in loops while implementing) always as both side are equivalent for us
so dp[i][j][k] is same as dp[i][k][j] .
This will reduce some computation.

21

So, do you also want me to Lock your “WRONG CODE” in the forum, humiliate it with proof?
Stop posting such shitty codes when it’s not at all relevant to the discussion.