Request for editorial of Placements problem of RECursion Challenge-I

contest
dynamic-programming
editorial
test-cases

#1

Problem is This



Can someone provide an editorial for the problem?

Or some test-cases to check where I am wrong.

Or my solution is This using DP, can someone see where I am wrong.

#2

@saurabh: Prerequisites: Subset generation

Now what you need to do is generate all the possible combinations of the books and store the minimum space left.
One condition that is needed to care if all the sizes of books are greater than capacity then answer will be capacity itself.
Hope you get it!


#3

It fails for this test case.

1
4 11
3 6 7 2
  • Your Output : 1
  • Correct Output : 0

I think your else block inside the loop is buggy. Check that.

else{
   dp*[j] = dp[i+1][j];
   if(arr*<=dp[i+1][j]) dp*[j] -= arr*;
}

Saurabh, I think now you can make your way. By the way, you can implement a recursive procedure (as suggested by above, for possible subset generation), which easily solves the problem, and them memoize it for further improvement. Infact, non-memoized version is also accepeted here. :slight_smile:


#4

Simply just generate all subsets (using bitmasking) and find the subset with largest sum which is also less than or equal to the self size.
my solution


#5

Just wanted to give this fact there, I did the question both ways(generating subsets), you may look here. The first way has recursion which takes just 0.04 sec while the sec takes 0.46 sec and it has no function calls.
The use of pow() function is basically the cause of such big time gap. Although I thought recursion can once give TLE because of calls.


#6

Okay, You are right, my solution is giving WA for the above case.
Anyway, isn’t there a DP solution for this problem. I mean subset generation is working just because n<=20, what if it would have been greater ?


#7

I think you can implement a top-down DP by memoizing the recursive solution. For bottom up, one can think of in terms of knapsack, but as range of bookshelf is large, you have to implement a space efficient version.