PROBLEM LINK:
Author: Gerald Agapov
Tester: Abdullah Al Mahmud
Editorialist: Vinod Reddy
DIFFICULTY:
HARD.
PREREQUISITES:
Flow,Greedy
PROBLEM:
We are given orders of the form (Si,Di,Xi,Pi) where Si and Di and starting and ending time slots and Xi is the number of the items to be prepared and Pi is the penalty for leaving out a single item of the order. We need to fill the time slots with items so that penalty is minimized.
QUICK EXPLANATION:
There are two approaches to the problem one min-cost flow which is a bit risky with time limits since you need the best implementation and another easily implementable greedy solution.
**FLOW SOLUTION : **
In the flow solution you have time slots on the left and orders on the right. for every order you will have an edge between order and the time slots it is given and the edge cost will be the penalty of the order and capacity 1. Here the no of slots are large. So you can divide total no of slots into ranges of slots such that every range can either be part of a order totally or not. This can be achieved easily and using them as nodes we can run the min-cost flow algorithm.
We approach a greedy solution where we process the tasks in order of decreasing penalty and at each step we try to accommodate maximum number of the items of the present order.
The second step(accommodating maximum number of items) can be solved using another greedy approach.Details are given below.
EXPLANATION:
First lets solve the following sub problem which will be used in the subsequent main solution.
Lets say we have k orders each with penalty 1. We need to know the minimum penalty now. this can be solved easily using a greedy approach. I will build the greedy approach in two steps.
**Step 1 :** Suppose now additionally let the Xi of all the orders be 1. Now if have to find the minimum penalty we can model it by finding a maximum matching in a bipartite graph where orders are nodes in the left side and slots are in the right side and range of every vertex in left is a contiguous number of nodes in right. This can be done very easily through greedy approach(I leave the actual algo for reader).
**Step 2 :** Now if we try to do it for orders where Xi can be anything we can emulate the above algorithm except only here the groups of nodes in right are allocated to a node in left. Though not practically feasible if it helps, you can visualize an order of Xi items as Xi orders with 1 item and same ranges and apply above algorithm.
**Main Solution :** In the main solution we process the orders in the order of their decreasing penalty. Lets say for the first k orders we didn't require to get any penalty. Now we are trying to allocate items of the (k+1)th task.For this we solve the above sub problem specified above for the k+1 tasks i.e assume penalty is 1 for all the tasks and get the penalty for first k+1 orders. Let this penalty be p. So the maximum matching will leave out p items. We can construct the new matching where the p items returned are only the items of order k+1 because when we trim the items of order k+1 to X_k+1-p and apply the algorithm the returned value will be 0.
Now we want the p items to be of order k+1 because order k+1 will have least penalty. We trim down the items of order k+1 to X_k+1-p and add the p items to global penalty and do this process for order k+2 and so on. Finally we will get the total minimum penalty.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.