WIPL - Editorial

rutuja2229 · January 12, 2021, 6:28pm

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.

vickyvanshaj · January 12, 2021, 6:33pm

I replied on your comment. Go take a look.

emotiological · January 12, 2021, 6:38pm

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.

harish_dalal · January 12, 2021, 6:53pm

A little bit different DP approach by me

karnikkanojia · January 13, 2021, 3:20am

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?

shivam51 · January 13, 2021, 3:40am

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

malayp_98 · January 14, 2021, 7:00am

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

karan_221 · January 14, 2021, 7:19am

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

avishek_pratap · January 14, 2021, 8:41am

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

pri191299 · January 14, 2021, 9:47am

Okay. Got it now. Thanks.

wh1ter0se · January 15, 2021, 6:03am

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

dhairy_coder · January 15, 2021, 10:38am

I have done using brutefore but used sets so repetitive calculations are avoided.
https://www.codechef.com/viewsolution/41519501

gb21 · January 17, 2021, 3:22pm

https://www.codechef.com/viewsolution/41692894
Did this using recursion, greedy. Doesn’t pass all the test cases though.

cubercoder · January 17, 2021, 4:52pm

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

ketan77 · January 17, 2021, 5:52pm

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

ketan77 · January 17, 2021, 5:53pm

Hello,can you please tell me which test case are not passing in my approach or whats wrong with my approach
Code:CodeChef: Practical coding for everyone

harshagrawal16 · January 17, 2021, 6:07pm

A different approach using bfs.

sandeepmandal4 · January 19, 2021, 2:38pm

So basically we are using knapsack method for the first tower and greedy method for second tower! is that right?

sagargoel · January 20, 2021, 8:09pm

N=9
K=20
15 15 4 3 3 4 3 4 4
Ans-6

taipon12 · January 20, 2021, 8:27pm

Hey ! Are test cases weak or something ?
Why my dp solution [CodeChef: Practical coding for everyone] is getting accepted which only memoizes sum of the two bags till ith index .I don’t think these are the only states that need to be stored.