PROBLEM LINK:Author: 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.
This question is marked "community wiki".
asked 24 Jan, 03:49
