PROBLEM LINK:
Author: Sergey Kulik
Tester: Kevin Atienza
Editorialist: Kevin Atienza
PREREQUISITES:
Graphs, min-cost flow
PROBLEM:
Given N dishes and D days, Sergey plans to eat all dishes within the D days. Here are some constraints:
- The probability of dish i appearing in day j is A_{i,j}.
- Sergey wants to maximize the overall probability of eating all dishes.
- He only plans on eating each dish in exactly one day. If he is unlucky that the dish didn’t appear in its assigned day, then sorry for him
(i.e. he cannot choose to plan to eat the same dish again in another day) - In any given day, he needs to plan to eat at least one dish (otherwise he’ll starve).
- His stomach can only allow up to K dishes per day.
Is the task possible? If it is, you also need to give the maximum overall probability, and one possible assignment of the dishes to the days which achieves this probability.
QUICK EXPLANATION:
It is guaranteed that A_{i,j} \ge 0.75, 1 \le D, K \le N and DK \ge N, so a solution is always possible (you can always assign the N dishes in a round-robin fashion among the D days).
This can be solved by reducing it to the minimum-cost flow. Construct a graph with N+D+2 nodes, one node f_i for each dish i, one node d_j for each day j, and a source S and sink T.
- Make an edge (S,f_i) for every dish i with capacity 1 and cost 0.
- Make an edge (f_i,d_j) for every dish i and day j with capacity 1 and the following cost: -\log(A_{i,j}) (which is positive).
- Make an edge (d_j,T) for every day j with capacity 1 and cost 0.
- Make another edge (d_j,T) for every day j with capacity K-1 and cost 100. We use the cost 100 because it is much larger than -50\log 0.75. (this special constraint is to ensure that he eats at least once each day)
- Find the minimum-cost max-flow, and assign dish i to day j if \text{flow}(f_i,d_j) = 1 (it can be shown that \text{flow}(f_i,d_j) is either 0 or 1 in the result). The final probability can be computed easily from this.
EXPLANATION:
Let’s first try to modify the problem slightly. Instead of using probabilities, we use log probabilities: we replace A_{i,j} with -\log A_{i,j} (the base of the logarithm does not matter). Now, instead of maximizing the overall product of probabilities, we are now minimizing the sum of log probabilities.
Let’s try to solve a simplified version of the problem. Consider the case where D = N. In other words, Sergey needs to eat exactly one dish per day and minimize the sum of the log probabilities. Notice that this is just an instance of the assignment problem! We have just shown that the assignment problem is a special case of this problem, i.e., our solution for the problem at hand should be powerful enough to at least solve the assignment problem.
How do you solve the assignment problem? It’s well-known that it can be solved by reducing it to an instance of the minimum-cost flow problem:
- First, realize that the assignment problem is equivalent to finding the minimum weighted perfect matching in a bipartite graph.
- Next, we can reduce minimum weighted perfect matching to the min-cost max-flow problem by creating two nodes, the source and the sink, attaching the source to half of the nodes and the sink to the other half, all with capacities equal to 1 and zero costs.
- Finally, run any standard min-cost max-flow algorithm (such as the successive shortest paths algorithm) on the given graph, and create a matching based on the flow between the two halves of the graph
The successive shortest paths algorithm with the Bellman-Ford algorithm will run in O((2N)^4), which should pass.
But it’s easy to generalize this solution to handle the additional constraints of this problem!
- There are D days instead of N, so we will need to create a bipartite graph with N nodes on one side and D nodes on the other.
- Sergey eats at most K dishes on each day, so the capacities between the D nodes and the sink should be K.
- Finally, we also need to ensure that Sergey eats at least one dish each day. Previously, in the assignment problem this is automatically guaranteed. However, in our case it’s possible that DK \gg N, so it’s possible that the optimal flow doesn’t assign any dishes to some days. To fix this, instead of making an edge from each of the D nodes to the sink with capacity K and cost 0, we split each such edge into two: one with capacity 1 and cost 0 (which we call the good edge), and another with capacity K-1 and a really large cost, say 100 (which we call the bad edge). We can show that the minimum-cost flow uses up all those good edges, because otherwise you will have to incur additional costs of 100 for every good edge you don’t use. But since 100 is very large (so large that 100 \gg -50\log 0.75), you cannot cancel out even a single 100 by optimizing the cost of the flow somewhere else in the graph. Therefore, we have shown that the minimum-cost flow uses up all good edges, and thus Sergey gets to eat at least one dish each day
We can now run the successive shortest paths algorithm on this modified graph to find an optimal assignment of days to dishes. Since there are N+D+2 nodes, this runs in O((N+D)^4) = O(N^4) time
Note: If you’re using an adjacency matrix to represent the graph (which is probably good because there are at least ND edges), you need to take special care because there are parallel edges (more precisely, D pairs of them: the good and bad edges). There are at least two techniques to fix this:
- First, we can add an additional node which we will call the pre-sink, and point the good edges to the pre-sink instead of the sink. Finally, we add an edge from the pre-sink to the sink with capacity D and cost 0. It can be shown that the minimum-cost flow for this modified graph is not affected.
- Another technique is to simply use two adjacency matrices. It uses twice the memory and possibly twice the runtime, but still it should pass the time limit if the min-cost flow algorithm is implemented well.
Time Complexity:
O((N+D)^4) = O(N^4)