CHEFGIRL - Editorial
#PROBLEM LINK:
[Contest][222]
**Author:** [][4444]
**Tester:** [][5555]
**Editorialist:** [Kevin Atienza][6666]
#PREREQUISITES:
Dynamic programming, directed graphs
#PROBLEM:
There is a directed acyclic graph representing people with the following properties:
- All nodes have at most one incoming edge.
- All nodes have at most one outgoing edge, except node $1$.
Person $1$ (node $1$) holds $32$ secrets, $[1-32]$. $[1,32]$. If there is an edge from $a$ to $b$, then $a$ tells secrets to $b$. But each edge has a range assigned to it, specifying which range of secrets that can be told.
If a node doesn't have an outgoing edge, she tells all the secrets she knows to Chef.
The following operation can be performed: take some edge, and extend its range by one (to the left or the right). What is the minimum number of operations for Chef to know all $32$ secrets?
#QUICK EXPLANATION:
The graph consists of paths all starting from node $1$, and are otherwise disjoint aside from node $1$.
For each such path, and each range $[i-j]$, $[i,j]$, compute the minimum number of operations to make sure all secrets $[i-j]$ $[i,j]$ can be told through that path.
For all ranges $[i-j]$, $[i,j]$, compute $\text{cost}(i,j)$, defined as the minimum number of operations to make sure the secrets $[i-j]$ $[i,j]$ reach Chef *through a single path*, among all paths.
Let $\text{best}(k)$ be the minimum $\sum_{[i-j] $\sum_{[i,j] \in P} \text{cost}(i,j)$ among all partitions $P$ of $[1-k]$ $[1,k]$ into subranges. (For example $\{[1-4],[5-9],[10-15]\}$ $\{[1,4],[5,9],[10,15]\}$ partitions $[1-15]$.) $[1,15]$.) The answer is $\text{best}(32)$, and the $\text{best}$s can be computed with dynamic programming.
#EXPLANATION:
The property that all nodes have at most incoming edge and at most one outgoing edge (except node $1$) actually limits the possible shapes that the input graph can be in. Essentially, there can't be any sort of *branching* into or out of any node except node $1$. This means that our graph is really just a bunch of disjoint paths all starting from node $1$. (The problem statement doesn't in fact exclude the possibility of there being paths that don't start at node $1$, but it seems these paths don't appear in the input.) This gives us a much easier time finding a solution, and also suggests looking at each path individually.
Consider a path from node $1$ to some node with no outgoing edge. The secrets that can pass through the two edges are those that belong in the *intersection* of the ranges assigned to all the edges in the path. But the intersection of two ranges is another range! This means that the **the secrets that can be relayed in a path is always some range range** (possibly empty).
This tells us that the way in which the secrets $[1-32]$ $[1,32]$ are relayed to Chef is by relaying subranges of $[1-32]$ **subranges** of $[1,32]$ through different paths until all secrets have reached Chef. For example, the range $[11-24]$ $[11,24]$ might be relayed through one path, the range $[28-29]$ $[28,29]$ through another path (possibly the same path as the previous), and $[23-26]$ $[23,26]$ in yet another, etc. For But for all secrets to be sent, the subranges must *cover* **cover** the subrange $[1-32]$. $[1,32]$.
Thus, it makes sense for us to compute the minimum number of operations to make sure send the secrets $[i-j]$ reach Chef $[i,j]$ through some path, say $p$. Let's denote this by $\text{cost}_p(i,j)$. In order for $[i-j]$ "$\text{cost}(p,i,j)$". For $[i,j]$ to be able to pass through this path, we only need to make sure that $[i-j]$ $[i,j]$ is contained in the ranges assigned to each edge of the path. It's easy to see that this is necessary and sufficient. So for every range $[a-b]$, $[a,b]$, we want to extend it so that it contains $[i-j]$, $[i,j]$, which is equivalent to saying that $a \le i \le j \le b$. It's easy to see that the minimum number of steps we need to accomplish this is $\max(0,a-i) + \max(0,j-b)$:
- $\max(0,a-i)$ steps (extending $[a-b]$ $[a,b]$ to the left) are needed to ensure that $a \le i$.
- $\max(0,j-b)$ steps (extending $[a-b]$ $[a,b]$ to the right) are needed to ensure that $b $j \le j$. b$.
Therefore, for a single path $p$ and range $[i-j]$ $[i,j]$ we can easily compute $\text{cost}_p(i,j)$ $\text{cost}(p,i,j)$ by adding this value for all edges in $p$.
Now, we want to relay the secrets $[1-32]$ using the $[1,32]$, and we have multiple paths that we have. to use. As said above, we know that we will send subranges of $[1-32]$ *subranges* through different paths, but things are a bit trickier because we don't know yet where to send each subrange through so that the total cost is minimized. Thankfully, there are a couple of observations that will make our search easier:
- We only need to send every secret at most once, so the set of subranges that cover $[1-32]$ $[1,32]$ can in fact be disjoint. Note that this doesn't mean that there is only one way for a particular secret to reach Chef. For example, suppose we send the subrange $[8-15]$ $[8,15]$ through one path and $[13-20]$ $[13,20]$ through another. These two subranges overlap, so we can replace the second with the smaller subrange $[16-20]$. $[16,20]$. Clearly, $\text{cost}_p(16,20)$ $\text{cost}(p,16,20)$ cannot be greater than $\text{cost}_p(13,20)$. $\text{cost}(p,13,20)$. (Why?)
- It doesn't make sense to send two *disjoint* subranges in the same path. Why? Consider for example sending $[3-6]$ and $[10-15]$ $[3,6]$ and $[10,15]$ through some path $p$ (assuming $[7-9]$ $[7,9]$ are sent through some other path). paths). However, remember from above that the set of secrets that can be relayed in a path is always some range, and the smallest range containing $[3-6]$ and $[10-15]$ is $[3-15]$, $[3,6]$ and $[10,15]$ is $[3,15]$, whuch contains $[7-9]$. $[7,9]$. This means we can assume instead that we are relaying $[3-15]$ $[3,15]$ through $p$ without incurring any additional cost. (Why?)
- Finally, it doesn't matter which path we send each subrange $[i-j]$ $[i,j]$ through. We only want the path that *minimizes* the cost. For example, if $\text{cost}_{p_1}(12,25) $\text{cost}(p_1,12,25) < \text{cost}_{p_2}(12,25)$, \text{cost}(p_2,12,25)$, then we can essentially ignore path $p_2$ when sending $[12-25]$ $[12,25]$ because there's always a way to send it with a smaller cost. (namely, through $p_1$) Thus, we can define the function $\text{cost}(i,j)$ to be the minimum $\text{cost}_p(i,j)$ $\text{cost}(p,i,j)$ among all paths $p$.
With these observations, the problem is now reduced to this:
*What is the minimum $\sum_{[i-j] $\sum_{[i,j] \in P} \text{cost}(i,j)$ among all partitions $P$ of $[1-32]$ $[1,32]$ into subranges?*
But this is easily solved with dynamic programming: Let $\text{best}(k)$ be the minimum $\sum_{[i-j] $\sum_{[i,j] \in P} \text{cost}(i,j)$ among all partitions $P$ of $[1-k]$ $[1,k]$ into subranges. (For example $\{[1-4],[5-9],[10-15]\}$ $\{[1,4],[5,9],[10,15]\}$ partitions $[1-15]$.) $[1,15]$.) Then the answer is $\text{best}(32)$, and the $\text{best}(k)$s has the following recurrence:
$$\text{best}(k) = \min_{1 \le j \le k} \left(\text{best}(j-1) + \text{cost}(j,k) \right)$$
The $j$ in this formula represents the leftmost endpoint of the rightmost range, $[j-k]$. $[j,k]$. The minimum total cost for the remaining subranges is $\text{best}(j-1)$.
The base case is $\text{best}(0) = 0$. Thus, after computing the $\text{cost}(i,j)$s for all ranges $[i-j]$, $[i,j]$, $1 \le i \le j \le 32$, the answer can now be computed easily!
#Time Complexity:
$O(NS^3)$ or $O(NS^2)$ where $S$ is the number of secrets. ($S = 32$)
#AUTHOR'S AND TESTER'S SOLUTIONS:
[setter][333]
[tester][444]
[222]: http://www.codechef.com/DEC15/problems/CHEFGIRL
[333]: The link is provided by admins after the contest ends and the solutions are uploaded on the CodeChef Server.
[444]: The link is provided by admins after the contest ends and the solutions are uploaded on the CodeChef Server.
[4444]: http://www.codechef.com/users/????
[5555]: http://www.codechef.com/users/????
[6666]: http://www.codechef.com/users/kevinsogo