At ACM ICPC SEERC 2009 was this problem:
Problem E.
I need a hint to solve it. My instinct tells me that some sort of dynamic programming would do. But I can't figure it out.
Problem E.
I need a hint to solve it. My instinct tells me that some sort of dynamic programming would do. But I can't figure it out.
States of the DP is a(i, j), where a(i,j) = minimum makespan when first application consists of procedures (1,i)(1,i+1)..(1, N), and second application consist of procedures (2,j).(2,j+1),...,(2,N). Thus there are O(n^2) DP states.
Now if we need to calculate a(i,j) then we try to go on both application i.e. execute corresponding procedures
until first collision happens. In this case there are some r and k that P(1,r)=P(2,k). Consider two possibilities - procudere (1,r) are waiting and procedure (2, k) are executing, and vice versa. So a(i,j) = min(T2 + a(r, k +1),
T1 + a(r + 1, k), where T1 is time first application to executes procedures (i,..., r), and T2 is time second application to executes procedures (j,..., k). Thus overall time complexity is O(N^3).
However, the time limit is tough and some optimizations are needed.
Here is the code that got accepted on this online judge.