MAXCOMP - Editorial

anton_lunyov · October 15, 2012, 3:00pm

PROBLEM LINK:

Practice
Contest

Author: Khadar Basha
Tester: Anton Lunyov
Editorialist: Anton Lunyov

DIFFICULTY:

SIMPLE

PREREQUISITES:

Dynamic Programming, Interval Scheduling

PROBLEM:

You are given a set of orders for conducting events. Each event has its starting hour, ending hour and a compensation for its conducting. The task is to find the set of orders with maximal possible compensation such that corresponding events do not overlap.

QUICK EXPLANATION:

Denote event with starting hour S and ending hour E as **(S, E)**−event. Since range of hours is small we can create a two-dimensional array C[0…48][0…48] with meaning C[S][E] is the maximal compensation among all **(S, E)**−events. For convenience we put C[S][E] = 0 if there are no **(S, E)**−events. Then the problem can be solved by dynamic programming. Denote by maxC[E] the maximal possible compensation if we consider only events with ending hour ≤ E. Then

maxC[0] = 0;
maxC[E] = max{maxC[S] + C[S][E] : 0 ≤ S < E}, for 1 ≤ E ≤ 48;

and the answer is maxC[48].

EXPLANATION:

The array C[0…48][0…48] should be filled initially with zeros:

for S from 0 to 48
    for E from 0 to 48
        C[S][E] = 0

Tip. In C/C++/Java you should create this array as: int C[49][49];

After that it can be filled with correct numbers just in the stage of reading information about orders. Namely, if order with parameters Si, Ei and Ci was read then you should replace C[S][E] by Ci if Ci is greater than the old value of C[S][E]:

read Si, Ei, Ci
C[Si][Ei] = max(C[Si][Ei], Ci)

The convention C[S][E] = 0 if we have no **(S, E)**−events can be treated as adding of dummy events with zero compensation for each such pair (S, E). Clearly adding of such events does not change the answer since their compensations are zeros. So now we have **(S, E)**−events (possibly dummy) for every pair (S, E) such that 0 ≤ S < E ≤ 48.

Now we explain the formula for maxC[E]. The part maxC[0] = 0 is obvious since we don’t have events with ending hour ≤ 0 and hence can’t get positive compensation. Now let 1 ≤ E ≤ 48. Recall that maxC[E] is the answer for the problem if we consider only events with ending hour ≤ E.

If we don’t have events with ending hour equals to E then the maximal possible compensation is not greater than maxC[E − 1] since all the remaining events lie on the segment [0, E − 1] and maxC[E − 1] is exactly the maximal possible compensation if all events has ending hour ≤ E − 1. Clearly, maxC[E − 1] ≤ maxC[E − 1] + C[E − 1][E].

Now assume that in optimal choice we have **(S, E)**−event with compensation C[S][E]. Since events should not overlap, all the remaining events lie on the segment [0, S], so the maximal possible compensation for them is maxC[S] by definition of this number. Hence, the total compensation in this case is maxC[S] + C[S][E]. Clearly, in order to get maxC[E], we should get the maximum of maxC[S] + C[S][E] over all S < E. So we arrive at the required formula for maxC[S][E].

The pseudo-code for this part of solution can be written as follows:

for E from 0 to 48
    maxC[E] = 0
    for S from 0 to E − 1
        maxC[E] = max(maxC[E], maxC[S] + C[S][E])
print maxC[48]

Thus, we get a solution with time complexity O(N + H * H) that requires O(H * H) memory, where H = 48 is the hour range. Here summand N corresponds to input stage while summand H * H corresponds to all other stages (initializing C[0…48][0…48], calculating DP). You can see an implementation of this approach in first tester’s solution.

ALTERNATIVE SOLUTION:

Now we discuss the solution that doesn’t make any assumptions on hour range. For this let’s save all events in some array and sort them in ascending order of ending hour. We number events from 1 to N and denote by S[i], E[i] and C[i] the corresponding parameters of the i-th event. Similarly to the previous solution denote by maxC[i] the maximal possible compensation we can get by using first i events of this sorted array. Denote also by ind[i] the largest index j such that j-th event does not overlap with i-th event. If all events with smaller indexes overlap with the i-th one we set ind[i] = 0. Then it is clear that

maxC[0] = 0;
maxC[i] = max(maxC[i − 1], maxC[ind[i]] + C[i]), for i from 1 to N;

and the answer is maxC[N].

Here first argument of maximum means that we do not take the i-th event, while the second argument means that we take it, and since the remaining events should not overlap with it we move to maxC[ind[i]].

The index ind[i] can be found by binary search. Indeed, ind[i] is the largest index j such that E[j] ≤ S[i]. So the following pseudo-code will find ind[i] in O(log N) time:

L = 0
R = i
while L + 1 < R do
    M = L + (R − L) / 2
    if E[M] ≤ S[i] then
       L = M
    else
       R = M
ind[i] = L

Thus we get a solution with time complexity O(N * log N) that requires O(N) memory, if we use some fast sorting algorithm like Quicksort or Merge sort. The complexity of each step is:

Input: O(N).
Sorting: O(N * log N).
Calculating ind[i] for each i: O(N * log N).
Calculating DP: O(N).
Also note that we don’t need actual array ind[1…N] since we can calculate it during calculation of DP, that is, we can unite 3-rd and 4-th steps together. See the second tester’s solution as a reference.

But in this problem you can find ind[i] in a simple O(N) loop since N is small enough, as well as use some simple O(N * N) sorting algorithm. See the setter’s solution as a reference.

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.
Tester’s first solution can be found here.
Tester’s second solution can be found here.