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

×

Stuck midway in Sanskar

I have managed to generate all the possible subsets of the required sum. Here is an idea of where I am : https://www.facebook.com/ajax/mercury/attachments/photo.php?fbid=1558562517694731&mode=contain&width=176&height=176 Now,since I can't chose (1,2,3,5) and (1,2,8) together I need K disjoint subsets which I have been thinking on how to get.I initially thought of storing all the pairs in a double dimensional array and then bruteforcing random K subsets if it works out.But I thought I won't be able to pass within the given time limit so I didn't apply this logic. This situation is similar to the problem Exact Cover which is NP Complete I guess. Also,keep DP as far away as possible from the solution because don't know it much. Thanks!

asked 15 Dec '14, 20:03

h1ashdr%40gon's gravatar image

2★h1ashdr@gon
2912319
accept rate: 10%

Here is my code so far : http://ideone.com/ML0zeR

(16 Dec '14, 02:43) h1ashdr@gon2★

have a look at the editorials and also look at the comments there .

sanskar editorials

link

answered 15 Dec '14, 20:09

acodebreaker2's gravatar image

1★acodebreaker2
1.2k12
accept rate: 18%

People seem to have attempted the problem in a different manner than I have attempted. I want to know if there is a path which leads to the correct output from where I have left off my solution.

(15 Dec '14, 20:12) h1ashdr@gon2★

The link above is broken. However, I think you are doing something this way.

link

answered 15 Dec '14, 23:53

damn_me's gravatar image

3★damn_me
2.6k21336
accept rate: 24%

Here is the code till the point I've reached : http://ideone.com/ML0zeR

(16 Dec '14, 02:43) h1ashdr@gon2★

This gives me all subsets of the required sum but since we can't take both (1,2,3) and (1,5) I need to code it after this step to take into consideration only disjoint k subsets.

(16 Dec '14, 02:45) h1ashdr@gon2★
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:

×57
×13
×13
×2

question asked: 15 Dec '14, 20:03

question was seen: 1,210 times

last updated: 16 Dec '14, 02:45