×

# Request for editorial of Placements problem of RECursion Challenge-I

 0 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. asked 26 Jan '15, 11:23 18●1●4 accept rate: 0%

 1 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[i][j] = dp[i+1][j]; if(arr[i]<=dp[i+1][j]) dp[i][j] -= arr[i]; }  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. :) answered 26 Jan '15, 12:39 85●4●8●14 accept rate: 22% 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 ? (26 Jan '15, 16:11) 1 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. (26 Jan '15, 19:26)
 1 @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! answered 26 Jan '15, 12:29 5★saanc 650●5●7●21 accept rate: 0%
 0 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 answered 26 Jan '15, 15:14 893●2●11●35 accept rate: 10%
 0 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. answered 29 Jan '15, 20:18 3★damn_me 2.6k●2●13●36 accept rate: 24%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,683
×2,172
×1,243
×361

question asked: 26 Jan '15, 11:23

question was seen: 2,301 times

last updated: 29 Jan '15, 20:18