PROBLEM LINK:
Author: Hasan Jaddouh
Tester & Editorialist: Hussain Kara Fallah
PROBLEM EXPLANATION
There are N people standing in a queue for Chef’s ice cream. They are numbered 1 through N from the front to the back of the queue.
Chef’s customers do not like to wait too long. For each valid i, we know that the ice cream ordered by the i_{th} person will take P_i seconds to prepare and cost V_i units of money, but if this person has to wait strictly more than W_i seconds in the queue (until Chef starts preparing their order), they will leave. At any time, it is only allowed to prepare the ice cream of the person standing at the front of the queue.
Chef wants to maximise his profit (the sum of prices of sold ice creams). In order to do that, he may choose to kick some of the customers (possibly nobody) out of the queue. Find the maximum profit Chef can make.
DIFFICULTY:
Easy - Medium
CONSTRAINTS
1\leq N \leq 40
PREREQUISITES:
None
Quick Explanation
Use meet in the middle approach. Divide the queue into 2 halves. For each half generate all valid subsets of people staying in the queue (subsets that no person should wait for more than his corresponding W). Iterate through subsets of the second half, for each subset find the maximum duration every person in the subset can wait for and take the smallest of them m_{rw} , and match it with a subset from the first half with total production \leq m_{rw}
EXPLANATION:
This problem is solved with meet in the middle approach. Divide our queue into 2 halves.
Let’s take the first half and generate all possible subsets of customers (if we pick a subset means that this subset of people is going to stay in the queue).
Assuming that we fixed a subset S with size K:
S=\{i_1,i_2,i_3,....,i_{K} \} ;; i_1<i_2<i_3<...<i_{K}
we need to check the following condition:
{\displaystyle \sum_{x \in S}^{}\,\sum_{y \in S}^{y < x}P_y \leq W_x}\,\,\,\,\,\,
It means that each person’s maximum waiting time must be more than or equal to total serving time of all people behind him. This can be checked on the fly. We don’t care about subsets not satisfying that.
Let’s denote by V_S the value of the subset and P_S the serving time of the subset:
{\displaystyle V_S =\sum_{x \in S}^{}V_x}
{\displaystyle P_S =\sum_{x \in S}^{}P_x}
Now let’s generate all subsets of second half, and satisfy the condition mentioned above in the same way. Now what’s remaining is merging subsets. We need to take care of only one extra condition. When merging 2 subsets S,T (in order) all customers in T will wait for extra P_S seconds. So in order to merge them, each customer in T must have at least P_S spare seconds he can wait for. Let’s denote this value by minWait_T
minWait_T= Min(W_x - \displaystyle \sum_{y \in T}^{y < x}P_x )\,\,\,\,\,\, among all (x \in T)
Now for each subset T in second half we need to match it with subset Q from first half where P_Q \leq minWait_T
Let’s store pair values (P_S,V_S) for all subsets in first half and make sure that the vector is striclty increasing w.r.t first value of the pair and strictly increasing w.r.t second value of the pair. If we maintain so we can match each subset from second half by doing a binary search on the sorted vector (or use c++ std::upper_bound).
Total Complexity: O(2^{(n/2)}\, log(2^{(n/2)}))
AUTHOR’S AND TESTER’S SOLUTIONS:
EDITORIALIST’s solution: Can be found here
