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

×

[closed] What is the intuition behind the solution of this DP problem ?

I am trying to solve Topcoder problem,In editorial it is given the solution uses bitmask technique. Any one please post the logic behind this problem.

asked 14 Dec '15, 17:38

pallesai's gravatar image

4★pallesai
176127
accept rate: 17%

closed 10 Aug, 18:37

vijju123's gravatar image

5★vijju123 ♦
9.5k213

The question has been closed for the following reason "Other" by vijju123 10 Aug, 18:37


-2

Looks like a Flow Shop scheduling problem with two "workstations" or "resources", aka F2|prmu|Cmax. The solution is to use Johnson's rule. You could hack up some intuitive implementation of that and not resort to Dynamic Programing (or brute force).

In the editorial they are searching for the solution in brute-force fashion( O(2^N * N) complexity ). Since N is constrained at 20 it is likely alright.

What they are doing is basicaly making 2^N sized table (the sum[]), which they fill with the completion time of "input" of every combination of the jobs. Then they fill the trickier best[] with actual completion time including "outputs" of given combination.

They are merely doing it in DP fashion(reusing intermediate values). Sum(Set) is Ai + sum(Set without Ai) for any i. And they try every path to completion time saving that in best[]. best[i] is simply the minimum known at the time before better path/order is found (and all orders are tried eventualy in the loop). You should really read the code like this:

foreach( subset/combination S ) foreach( job J not yet in that subset ) allowedStart = allowed starting time of J's output( that is best[S] or end of input of J, whichever comes later ) newBestCandidate = allowedStart + output time of J if newBestCandidate < best[S with J] best[S with J] = newBestCandidate return best[all jobs included]

link

answered 14 Dec '15, 19:40

kr0oze's gravatar image

0★kr0oze
1023
accept rate: 41%

edited 16 Dec '15, 08:25

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:

×1,249
×48

question asked: 14 Dec '15, 17:38

question was seen: 806 times

last updated: 10 Aug, 18:37