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.
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]