You are not logged in. Please login at to post your questions!


Request for editorial of Placements problem of RECursion Challenge-I

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

saurabh2561's gravatar image

accept rate: 0%

edited 26 Jan '15, 11:23

It fails for this test case.

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

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

   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

ks2bmallik's gravatar image

accept rate: 22%

edited 26 Jan '15, 12:44

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) saurabh25613★

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) ks2bmallik2★

@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

saanc's gravatar image

accept rate: 0%

edited 26 Jan '15, 12:31

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

dragonemperor's gravatar image

accept rate: 10%

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

damn_me's gravatar image

accept rate: 24%

toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "title")
  • 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:


question asked: 26 Jan '15, 11:23

question was seen: 2,301 times

last updated: 29 Jan '15, 20:18