You are not logged in. Please login at www.codechef.com 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

3★saurabh2561
1814
accept rate: 0%

edited 26 Jan '15, 11:23


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. :)

link

answered 26 Jan '15, 12:39

ks2bmallik's gravatar image

2★ks2bmallik
854814
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★
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) 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!

link

answered 26 Jan '15, 12:29

saanc's gravatar image

5★saanc
6505721
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

link

answered 26 Jan '15, 15:14

dragonemperor's gravatar image

3★dragonemperor
89321135
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.

link

answered 29 Jan '15, 20:18

damn_me's gravatar image

3★damn_me
2.6k21336
accept rate: 24%

toggle preview
Preview

Follow this question

By Email:

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

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "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:

×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