WIPL - Editorial

editorial
, , , , ,
54

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

55

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

56

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

57

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

58

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

59

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

60

A different approach using bfs.

61

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

62

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

63

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.

64

Applying your logic getting TLE in 2nd subtask.
Can anyone please check this…
https://www.codechef.com/viewsolution/41784826

65

Why (n-i) will be the answer can you please explain? Why not take the least i for which the condition holds?

66

@pm_5289 We are considering the last i elements so for example if I choose the last 2 boxes, then the index i will be n-2. Hence number of boxes required will be n - (n-2) = 2.
Makes sense, right?

67

Hi can anyone tell me what’s the problem with my code? I’ve just started doing these practice problems and so my thinking for solving these problems hasn’t yet developed. So this code might look crap but I would greatly appreciate it if someone could point out the exact issue.

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

Thanks.

68

I think the tallest ones would result in minimum number of boxes required…

69

This is really nice!

70

Hey, I tried some minor changes that might speed up the solution and it worked for most of the test cases.

Only got 2 TLE for TCs.

I used PYPY3 compiler.

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

I guess few more changes or using Fast IO from PyRival template could enhance the speed further.

Also try PYPY2, python 2 for further speed improvements.

I m positive, you can get this solution AC.

71

Getting TLE in python for the same approach…

72

@shivam51 I have used non increasing array and prefix sum, with same knapsack approach as discussed in editorial, but getting wrong answer. Can you tell me what’s problem with my Code ?

73

Brother you nailed it.Even better than the editorial