Pls help, you are genius man

https://www.codechef.com/LTIME95B/problems/BENCHP/

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

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

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

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

1 Like

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

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

Oh yes! My bad :slight_smile:

1 Like

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

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

1 Like

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

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

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

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

yep

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

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

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

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

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.

(post withdrawn by author, will be automatically deleted in 24 hours unless flagged)