WIPL - Editorial

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.:blush:

I replied on your comment. Go take a look.

1 Like

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.

1 Like

A little bit different DP approach by me

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 :slight_smile:

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

I recommend solving Dividing Coins problem. I used solution to this as a subpart of WIPL.

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.

1 Like

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.

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

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

A different approach using bfs.