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

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.

@cubefreak777 please have a look at the problem. I am not able to solve it till now.

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.

@hello_everyone someone solved that question partially and got 90.9 score, and me only 54 pls help