Need help on a problemset in a programming contest
- by topher
I've attended a local programming contest on my country. The name of the contest is "ACM-ICPC Indonesia National Contest 2013".
The contest has ended on 2013-10-13 15:00:00 (GMT +7) and I am still curious about one of the problems.
You can find the original version of the problem here.
Brief Problem Explanation:
There are a set of "jobs" (tasks) that should be performed on several "servers" (computers).
Each job should be executed strictly from start time Si to end time Ei
Each server can only perform one task at a time.
(The complicated thing goes here) It takes some time for a server to switch from one job to another.
If a server finishes job Jx, then to start job Jy it will need an intermission time Tx,y after job Jx completes. This is the time required by the server to clean up job Jx and load job Jy.
In other word, job Jy can be run after job Jx if and only if Ex + Tx,y = Sy.
The problem is to compute the minimum number of servers needed to do all jobs.
Example:
For example, let there be 3 jobs
S(1) = 3 and E(1) = 6
S(2) = 10 and E(2) = 15
S(3) = 16 and E(3) = 20
T(1,2) = 2, T(1,3) = 5
T(2,1) = 0, T(2,3) = 3
T(3,1) = 0, T(3,2) = 0
In this example, we need 2 servers:
Server 1: J(1), J(2)
Server 2: J(3)
Sample Input:
Short explanation: The first 3 is the number of test cases, following by number of jobs (the second 3 means that there are 3 jobs for case 1), then followed by Ei and Si, then the T matrix (sized equal with number of jobs).
3
3
3 6
10 15
16 20
0 2 5
0 0 3
0 0 0
4
8 10
4 7
12 15
1 4
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
4
8 10
4 7
12 15
1 4
0 50 50 50
50 0 50 50
50 50 0 50
50 50 50 0
Sample Output:
Case #1: 2
Case #2: 1
Case #3: 4
Personal Comments:
The time required can be represented as a graph matrix, so I'm supposing this as a directed acyclic graph problem.
Methods I tried so far is brute force and greedy, but got Wrong Answer. (Unfortunately I don't have my code anymore)
Could probably solved by dynamic programming too, but I'm not sure.
I really have no clear idea on how to solve this problem.
So a simple hint or insight will be very helpful to me.
