I read your whole blog its Great thank you for this, but can u please explain the part u did * a| b* and then fill the values in dp array inshort the last part of that function.

I replied on your comment. Go take a look.

Your approach is greedy. But in some problems greedy wonât land you global optimum, therefore dp comes in.

Like in âstandard coin change problemâ if we try to make a change, firstly using large denominations then going for less, this is greedy approach and wonât always give you minimum coins you need to pick.

I just wanted to ask if there is a difference if we take to fill the DP array from top to bottom style rather than bottom-up. Is there a difference between both?

There should be no difference. You can use recursion and fill the dp[][] top to bottom

the code is only running for subtask 1, i don,t think this question can be done using greedy.

I was going through solutions section to see what are the different approach to solve this problem and I got this one https://www.codechef.com/viewsolution/41059309 . I guess he used bitmasking but I am not getting the logic. Can anyone explain ? @sksama @shivam51

Okay. Got it now. Thanks.

Very good explanation. I was also thinking of this problem as a subset sum problem but couldnât figure out how to implement.

I have done using brutefore but used sets so repetitive calculations are avoided.

https://www.codechef.com/viewsolution/41519501

https://www.codechef.com/viewsolution/41692894

Did this using recursion, greedy. Doesnât pass all the test cases though.

This is a bitset implementation of subset sum problem. Itâs a standard thing that was mentioned in the editorial as well. Even I learnt this technique after this contest only.

Refer to Gfg page for better explanation, it might take little time to digest but itâs one of the most efficient ways to implement subset sum

https://www.codechef.com/viewsolution/41696157

This is my code for watching CPL problem,its kind of bruteforce approach,can anyone tell me which test case it is not passing,it will be a great help

Hello,can you please tell me which test case are not passing in my approach or whats wrong with my approach

Code:Solution: 41696157 | CodeChef