PROBLEM LINK:
Author: Michael Nematollahi
Tester: Teja Vardhan Reddy
Editorialist: Michael Nematollahi
PREREQUISITES:
DP, range query data structures (like segment trees)
EXPLANATION:
Let’s call the dissatisfactions of the first type, the dissatisfactions of type ‘A’ and the dissatisfactions of the second type, the dissatisfactions of type ‘B’. For the sake of simplicity, let’s assume both t and s are increasing.
It’s not hard to see that it’s optimal for any passenger to board a bus as soon as they can. This is to avoid gaining type ‘B’ dissatisfactions. This means that for some array z of length M, the first z_1 persons board the first bus, the next z_2 persons board the second bus and so on.
The second observation to make is that once the last passenger of a bus gets on, it’s optimal for that bus to leave immediately to avoid raising type ‘A’ dissatisfactions. This implies that we only need to consider the times that are given in the input.
Let’s insert all the times given in the input in an array r and sort it. Note that every time has a corresponding person or bus. Let’s define dp[i] as the answer for the first i times. By this, I mean what would the answer be if the only buses were the ones among the first i times and the only persons were the ones among the first i times? It’s obvious that the answer to the original problem is dp[n+m].
Let’s find out how to calculate dp[i]. Note that we know what the last bus among the first i times is. Let’s call it last and the bus before it prev. To calculate dp[i], we need to choose a j where prev \leq j \lt i, which means last will take care of passengers with times from j+1 up to i and the rest of the passengers should be taken care of by the previous buses. For this choice of j, dp[i] would be dp[j] + the dissatisfaction of those that get on last. So a trivial solution with a bad complexity is to loop over j and find the minimum value.
Consider a passenger k where j \lt k \leq i. k will gain dissatisfaction of type ‘A’ iff the time of j is greater than s_k - a_k and less than s_k. Note that this represents a range.
k will gain dissatisfaction of type ‘B’ iff the i^{th} time is at least s_k + c_k. In other words, d_k should be added to all $dp$s that are before k once the i^{th} time exceeds that amount (note that we’re looping over i).
Both of the above cases add dissatisfactions to a range of $dp$s. Hence, we can keep the dp values in a segment tree that supports range addition and minimum queries and use addition queries to take care of the dissatisfactions. This enables us to calculate dp[i] with a range minimum query in O(log(n+m))
The total complexity of this solution is O((n+m) \times log(n+m)). Refer to the setter’s code to see the implementation.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.