PROBLEM LINK:
Editorialist: Adithya Dsilva
DIFFICULTY:
EASY-MEDIUM
PREREQUISITES:
PROBLEM:
You are given N + M tasks. You can perform only one task at a time, and the next task can be taken up only after finishing the current task.
Array C, consisting of N tasks is given where, C_n \, (1 \le n \le N) corresponds to the time required to finish task n.
Array P, consisting of M tasks is given where, P_m \,(1 \le m \le M) corresponds to the time required to finish task m.
Array T is given where, at time T_m \, (1 \le m \le M), P_m must be the task being processed. More formally, if P_m starts at s_m (unit time), then s_m \le T_m < s_m + P_m.
C_n (1 \le n \le N) can be started only after C_1, C_2, \dots, C_{n-1} have finished.
Determine the minimum time required to finish all tasks, where tasks can be allocated starting at unit time 1 itself.
QUICK EXPLANATION:
Tasks in P must be executed according to the order in which they must be processed (as given in T).
The question is now finding the minimum time required to finish executing N+M tasks. The last task to be run is either C_N or P_M. This can be used to form a recurrence, whose skeleton is as follows:
int Minim(int n, int m){
return min(C[n] + Minim(n - 1, m), Cost(m) + Minim(n, m - 1));
}
Cost(m) manages the constraints given on the execution of P_m such that a valid (or invalid, if no valid ordering exists) time is chosen to execute task P_m.
This can be easily converted to a DP, with states [N+1][M+1] (+1 because of the state of execution of 0 tasks of a particular type).
Converting the recursion from top-down to bottom-up is required to pass the TL.
EXPLANATION:
Points to be noted:
-
C, P, T in this editorial have multiple reference’s. C_i refers to both i^{th} task of C and time required by the i^{th} task in C. Same follows for P and T also. However, the editorial is quite clear, and leaves no scope for confusion
. - The editorial follows 1-based indexing.
-
llrefers tolong long intinC++. - INF is set as 1e15 as no combination of tasks (complying with the constraints) require a minimum of 1e15 to finish processing. Details are given at the bottom of the editorial.
-
T and P are merged into a
vector of pairsin the final solution.
Statement: Tasks in P must be processed according to the priority of their execution (as given in T). A formal explanation of the term priority is as follows: If T_{m} < T_{m_1} P_m has more priority than P_{m_1}.
Proof: Left to the reader.
Hint
Use the fact that only 1 task can be run at a particular time on the machine, and any sequence that doesn’t follow the given statement (above) leads to multiple tasks being executed at a particular time (which is not valid).
Imagine P_1 and P_2 have to be run at time 5 and 10 respectively. Thus, time of execution of task P_1 \le 5. If task P_2 were to be run before P_1, such that task P_2 is processed at unit time 10, which task would be running at time 5?
Thus, arrays C and P have a fixed order on how they must be executed. The order of processing tasks in P is based on the priority of their corresponding values in sorted array T.
All reference’s of P from this point forward represent P, sorted according to the order of execution. The corresponding values of T are also re-arranged.
Now, if all N+M tasks have been processed, the last task to be executed is either C_N or P_M.
In the first case, M tasks of P and N - 1 tasks of C are first executed in some order, such that the total time taken to process these tasks is minimised. Task C_N is then processed, and the time it takes is added.
It follows similarly for the second case also (while managing the constraints specified in T). What would this look like in machine code format?
return min(C[N] + Minim(N - 1, M), Cost(M) + Minim(N, M - 1))
\text{Minim}(n,m) refers to the minimum time it takes to process n+m tasks of C and P respectively. The details of \text{Cost}(M) have been described after the next snippet.
The recurrence for (N, M) also holds true for all valid n, m.
Does this look like a recurrence? Can we try to form the skeleton of the recursion?
int Minim(int n, int m){
return min(C[n] + Minim(n - 1, m), Cost(m) + Minim(n, m - 1));
}
//ans = Minim(N, M)
Here, \text{Cost}(m) is a dynamic function (and requires the value of \text{Minim}(n,m-1) to compute itself) that determines the time at which P_m should be executed so that, it’s execution fit’s within the constraints as mentioned by T_m, while minimising the overall time taken.
The exact specifications of \text{Cost}(m) is stated below. There are exactly 3 possible cases, which is handled by \text{Cost}(m).
- If \text{Minim}(n,m-1) > T_m, P_m can’t be executed in this case, as one among the n + (m-1) tasks is executed during time T_m (This is true since \text{Minim}(n,m-1) returns the least time required to execute these n+(m-1) tasks in a valid order). Thus this case should return INF. Why? Because the function call asks for
min, and returning INF complies this option is not possible. - If \text{Minim}(n,m-1) + P_m < T_m, we execute task P_m such that, the last unit time of execution is exactly T_m (Greedy logic). This is to minimise the overall time taken while executing it keeping in mind the time at which it should be processed.
- If \text{Minim}(n,m-1)<T_m and \text{Minim}(n,m-1) + P_m \ge T_m, \text{Cost}(m) should return \text{Minim}(n,m-1)+P_m. This is because executing task P_m right after time \text{Minim}(n,m-1) is valid (since it’s being processed at time T_m), and also minimises the overall time taken (Greedy logic again!).
It can be easily proved that these are the only 3 cases!
Thus, function \text{Cost}(m) incorporated into the recurrence is as follows:
int Minim(int n, int m){
int Cost;
//Computing Cost(m). Cost = Cost(m) + Minim(n, m - 1), done
//to simplify the entire equation that would follow otherwise!
if(Minim(n, m - 1) > T[m]) Cost = INF;
else if(Minim(n, m - 1) + P[m] < T[m]) Cost = T[m];
else Cost = Minim(n, m - 1) + P[m];
return min(C[n] + Minim(n - 1, m), Cost);
}
\text{Minim}(n,m-1) is being computed multiple times in the above recurrence (to help you to grasp what’s happening), but ideally should be computed only once.
Wait. Why is computing C_n when it’s the last task (C[n] + Minim(n - 1, m)) so simple and straightforward? This is simply because array C has no constraints on the time of execution, so executing it the right after the execution of the previous tasks, minimises the overall time taken (Greedy). It might overlap with some value given in T but that doesn’t really matter, as it will be handled by the corresponding value in C later on (Cost(m) handles it).
Calling \text{Minim}(N, M) returns the answer!
A very basic observation of the above recurrence leads us to the fact that there exists overlapping sub-problems. This can be solved by using DP and pre-computing the results.
Let us now try to form the states for the DP. The solution can be uniquely represented by the time it takes to finish the first i and k tasks of C and P respectively.
This can be directly seen by the variables in the function call of the recurrence. Thus, the DP states are [N + 1][M + 1] (+1 because of execution of 0 tasks of a particular type).
Now that we know the entire recurrence of the DP, lets convert it to a bottom-up approach (Seems like top-down approach doesn’t pass, TL is strict).
Since computing DP[n][m] requires both DP[n-1][m] and DP[n][m-1], both n and m in DP[n][m] have to be computed in increasing order starting from n = 0 and m = 0 (easy to logically verify this is true).
BARE CASES:
DP[0][0] = 0, since executing zero tasks takes 0 time.
Out-of-bound cases should be handled using if-else loops (n = 0 or m = 0).
If no valid order is possible for the first n and m tasks of C and P, DP[n][m]=INF.
If DP[N][M] = INF, there is no valid ordering of the tasks, hence output “-1" (without quotes).
Remember to use long long int to prevent overflows!
Justification for the value of INF
I’m not going to detail out the constraints here. You are advised to read them yourself from the question.
The last task in P would have worst case, 1e9 starting time. Thus all M-1 tasks are executed before time 1e9. Worst case, task P_M requires 1e9 time to get processed.
\therefore All M tasks of P were executed by time 10^9+10^9 = 2*10^9.
Assume all the tasks in P were to be executed in such a way such that no task from C could be executed before all M tasks were over. If C_1 = C_2 = \dots = C_N = 10^9, total time of executing these tasks would be N*10^9.
Thus overall time required to execute all N+M tasks would be 2*10^9 + N*10^9. Substituting max value of N yields : 2*10^9 + 5*10^3*10^9 < 10^{13}.
Thus value of INF is greater than max possible time required.
SOLUTION SNIPPET:
ll DP[N + 1][M + 1] = {};
DP[0][0] = 0; //Base Case
for(int n = 0; n <= N; n++){
for(int m = 0; m <= M; m++){
if(n or m) DP[n][m] = INF; //Setting everything to INF, while
//excluding DP[0][0]
//The min(...) computed simultaneously is done seperately
//to reduce variable clutter
if(m){
ll Cost;
if(DP[n][m - 1] > T[m]) Cost = INF;
else if(DP[n][m - 1] + P[m] < T[m]) Cost = T[m];
else Cost = DP[n][m - 1] + P[m];
DP[n][m] = Cost; //Cost variable exists for consistency with
//the editorial!!
}
if(n){
DP[n][m] = min(DP[n][m], DP[n - 1][m] + C[n]);
//Min computed here. Remember DP[n][m] = Cost from above.
}
}
}
if(DP[N][M] == INF) //No valid ordering possible
cout << "-1";
else //The answer!
cout << DP[N][M];
cout << '\n';
TIME COMPLEXITY:
Since there are N*M states of the DP, and calculating every state takes O(1), total time complexity per test case is O((N+1)*(M+1)).
The total time complexity is thus
MEMORY COMPLEXITY:
Memory complexity of DP array is
SOLUTIONS:
Editorialists solution can be found here.
If anyone manages to get an AC recursive solution (using only C++ or Java), add the link in the comments below, and I’ll add the solution here (along with credits)!
Did you like the editorial? Do you have any other approaches to the problem? Any suggestions? Comment them below!
Experimental: For better evaluation of my editorials, I request all readers to rate the editorial (on a scale from 1-5, where 5 represents an awesome 
editorial)
- 1
- 2
- 3
- 4
- 5
0 voters
Also don’t forget to up-vote this post if you liked it !
