Answers to: CHEFGIRL - Editorialhttps://discuss.codechef.com/questions/77642/chefgirl-editorial<h1>PROBLEM LINK:</h1>
<p><a href="http://www.codechef.com/DEC15/problems/CHEFGIRL">Contest</a><br>
<a href="http://www.codechef.com/problems/CHEFGIRL">Practice</a> </p>
<p><strong>Author:</strong> <a href="http://www.codechef.com/users/berezin">Dmytro Berezin</a><br>
<strong>Tester:</strong> <a href="http://www.codechef.com/users/xcwgf666">Sergey Kulik</a><br>
<strong>Editorialist:</strong> <a href="http://www.codechef.com/users/kevinsogo">Kevin Atienza</a></p>
<h1>PREREQUISITES:</h1>
<p>Dynamic programming, directed graphs</p>
<h1>PROBLEM:</h1>
<p>There is a directed acyclic graph representing people with the following properties:</p>
<ul>
<li>All nodes have at most one incoming edge.</li>
<li>All nodes have at most one outgoing edge, except node $1$. </li>
</ul>
<p>Person $1$ (node $1$) holds $32$ secrets, $[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 the range of secrets that can be told "through" this edge.</p>
<p>If a node doesn't have an outgoing edge, she tells all the secrets she knows to Chef.</p>
<p>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?</p>
<h1>QUICK EXPLANATION:</h1>
<p>The graph consists of paths all starting from node $1$, and are otherwise disjoint aside from sharing node $1$. </p>
<p>For each such path, and each range $[i,j]$, compute the minimum number of operations to make sure all secrets $[i,j]$ can be told through that path. </p>
<p>For all ranges $[i,j]$, compute $\text{cost}(i,j)$, defined as the minimum number of operations to make sure the secrets $[i,j]$ reach Chef <em>through a single path</em>, among all paths. </p>
<p>Let $\text{best}(k)$ be the minimum $\sum_{[i,j] \in P} \text{cost}(i,j)$ among all partitions $P$ of $[1,k]$ into subranges. (For example $P = \{[1,4],[5,9],[10,15]\}$ partitions $[1,15]$.) The answer is $\text{best}(32)$, and the $\text{best}(k)$s can be computed with dynamic programming, using the following recurrence:
$$\text{best}(k) = \min_{1 \le j \le k} \left[\text{best}(j-1) + \text{cost}(j,k) \right]$$</p>
<h1>EXPLANATION:</h1>
<p>The property that all nodes must have at most incoming edge and at most one outgoing edge (except node $1$) limits the possible shapes the input graph can be in. Essentially, there can't be any sort of <em>branching</em> 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 makes things much easier for us, and also suggests looking at each path individually. </p>
<p>Consider a path from node $1$ to some node with no outgoing edge. Thus, when a secret reaches the end of this path, it also reaches Chef. In fact, the secrets that can pass through this path are those that belong in the <em>intersection</em> of the ranges assigned to all the edges in the path. But the intersection of two ranges is another range! This means that <strong>the set of secrets that can be relayed in a path is always some range</strong> (possibly empty). In other words, if secrets $a$ and $b$ can be relayed through a path, then all secrets between $a$ and $b$ can also be.</p>
<p>This tells us that the way in which the secrets $[1,32]$ are relayed to Chef is by relaying <strong>subranges</strong> of $[1,32]$ through different paths until all secrets have reached Chef. For example, the subrange $[11,24]$ might be relayed through one path, the subrange $[28,29]$ through another path (or maybe the same path), and $[23,26]$ in yet another, etc. But for all secrets to be sent, the subranges must <strong>cover</strong> the subrange $[1,32]$. </p>
<p>Thus, it makes sense for us to compute the minimum number of operations to send the secrets $[i,j]$ through some path, say $p$. Let's denote this by "$\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]$ 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]$, we want to extend it so that it contains $[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)$: </p>
<ul>
<li>$\max(0,a-i)$ steps (extending $[a,b]$ to the left) are needed to ensure that $a \le i$. </li>
<li>$\max(0,j-b)$ steps (extending $[a,b]$ to the right) are needed to ensure that $j \le b$. </li>
</ul>
<p>Therefore, for a single path $p$ and range $[i,j]$ we can easily compute $\text{cost}(p,i,j)$ by summing this value for all edges in $p$. </p>
<p>Now, we want to relay the secrets $[1,32]$, and we have multiple paths to use. As said above, we know that we will send <em>subranges</em> 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: </p>
<ul>
<li>We only need to send every secret at most once, so we can in fact assume that the set of subranges that cover $[1,32]$ are <em>disjoint</em>. (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]$ through one path and $[13,20]$ through another. These two subranges overlap, so we can replace the second with the smaller subrange $[16,20]$. Clearly, $\text{cost}(p,16,20)$ cannot be greater than $\text{cost}(p,13,20)$. (Why?)</li>
<li>It doesn't make sense to send two <em>disjoint</em> subranges in the same path. Why? Consider for example sending $[3,6]$ and $[10,15]$ through some path $p$ (assuming $[7,9]$ are sent through other paths). However, remember from above that if two secrets can be relayed through a path, then all secrets in between them can also be, too. Thus, secrets in the range $[7,9]$ can also be relayed here too (without incurring any additional cost)! This means we can assume instead that we are relaying $[3,15]$ through $p$. </li>
<li>Finally, it doesn't matter which path we send each subrange $[i,j]$ through. We only want the path that <em>minimizes</em> the cost. For example, if $\text{cost}(p_1,12,25) < \text{cost}(p_2,12,25)$, then we can essentially ignore path $p_2$ when sending $[12,25]$ because there's 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)$ among all paths $p$. </li>
</ul>
<p>With these observations, the problem is now reduced to this:</p>
<p><em>What is the minimum $\sum_{[i,j] \in P} \text{cost}(i,j)$ among all partitions $P$ of $[1,32]$ into subranges?</em> </p>
<p>But this is easily solved with dynamic programming: Let $\text{best}(k)$ be the minimum $\sum_{[i,j] \in P} \text{cost}(i,j)$ among all partitions $P$ of $[1,k]$ into subranges. (For example $\{[1,4],[5,9],[10,15]\}$ partitions $[1,15]$.) Then the answer is $\text{best}(32)$, and $\text{best}(k)$ 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]$. The minimum total cost for the remaining subranges is $\text{best}(j-1)$. </p>
<p>The base case is $\text{best}(0) = 0$. Thus, after computing the $\text{cost}(i,j)$s for all ranges $[i,j]$, $1 \le i \le j \le 32$, the answer can now be computed easily using this DP solution!</p>
<h1>Time Complexity:</h1>
<p>$O(NS^3)$ or $O(NS^2)$ where $S$ is the number of secrets. ($S = 32$)</p>
<h1>AUTHOR'S AND TESTER'S SOLUTIONS:</h1>
<p><a href="https://www.codechef.com/download/Solutions/DEC15/Setter/CHEFGIRL.cpp">Setter</a><br>
<a href="https://www.codechef.com/download/Solutions/DEC15/Tester/CHEFGIRL.cpp">Tester</a><br>
<a href="https://www.codechef.com/download/Solutions/DEC15/Editorialist/CHEFGIRL.py">Editorialist</a> </p>enWed, 23 Dec 2015 16:07:46 +0530Answer by deep1996https://discuss.codechef.com/questions/77642/chefgirl-editorial/77944<p>nice editorial. :) </p>deep1996Wed, 23 Dec 2015 16:07:46 +0530https://discuss.codechef.com/questions/77642/chefgirl-editorial/77944Answer by parijat_196https://discuss.codechef.com/questions/77642/chefgirl-editorial/77904<p><a href="/users/81699/shubh_gupta_">@shubh_gupta_</a> can you please explain how to do it using dijkstra</p>parijat_196Tue, 22 Dec 2015 12:07:04 +0530https://discuss.codechef.com/questions/77642/chefgirl-editorial/77904Answer by vinay_goel21https://discuss.codechef.com/questions/77642/chefgirl-editorial/77842<p>Can anyone help me find out the cases I am missing.Here's my code: <a href="https://www.codechef.com/viewsolution/8984526">https://www.codechef.com/viewsolution/8984526</a>
I first identified all the girls chef can take information from.Then I traversed from 1-32.And then I identified the girl which gives minimum steps for that particular secret.For that particular girl i altered its edge and the edges of the intermediate girls to get the secret,also if that provides chef other secrets i mark them as found and don't perform the above procedure for them.The secrets are treated independently,for example, when i look for 7th secret i look for minimum steps to get only 7,not 1+2+..+7.</p>vinay_goel21Sun, 20 Dec 2015 17:30:07 +0530https://discuss.codechef.com/questions/77642/chefgirl-editorial/77842Answer by shubh_gupta_https://discuss.codechef.com/questions/77642/chefgirl-editorial/77829<p>This problem can also be solved using Dijkstra's shortest path algorithm using greedy approch.</p>shubh_gupta_Sat, 19 Dec 2015 20:20:11 +0530https://discuss.codechef.com/questions/77642/chefgirl-editorial/77829Answer by code_hard123https://discuss.codechef.com/questions/77642/chefgirl-editorial/77723<p>well the testcases were definitely weak i must say..
Because my this solution : -> <a href="https://www.codechef.com/viewsolution/8949979">https://www.codechef.com/viewsolution/8949979</a> passed for 90 points but it shouldnt since it failed for many testcases.
I was continously getting wrong answer for subtask 1.
then I made slight modification on my code ,and it passed subtask 1 but now was getting wrong answer for subtask 2.
here it is -> <a href="https://www.codechef.com/viewsolution/8952768">https://www.codechef.com/viewsolution/8952768</a> </p>
<p>I merged both of them and got 100 :D
my 100 pt solution : - > <a href="https://www.codechef.com/viewsolution/8952904">https://www.codechef.com/viewsolution/8952904</a> </p>
<p>I really wanna know why this happened. :D :) </p>code_hard123Tue, 15 Dec 2015 14:38:25 +0530https://discuss.codechef.com/questions/77642/chefgirl-editorial/77723Answer by englishhttps://discuss.codechef.com/questions/77642/chefgirl-editorial/77708<p>Link to the code is broken. Kindly fix it.</p>englishTue, 15 Dec 2015 01:30:06 +0530https://discuss.codechef.com/questions/77642/chefgirl-editorial/77708Answer by shikharidhttps://discuss.codechef.com/questions/77642/chefgirl-editorial/77693<p>The test cases were weak.. even solution which take all pair's of leaf nodes and calculate the answer passed the large tests.
I even posted a comment on the 6th day of the contest.. it is yet to be approved by the admin.Such repeated lethargy by the codechef team is only ruining the image of the platform.
P.S. - The last such incident was in the previous cook-off.Wrong solutions passed the system tests for the first problem.Some people posted regarding it, but nothing was done..</p>shikharidMon, 14 Dec 2015 20:05:54 +0530https://discuss.codechef.com/questions/77642/chefgirl-editorial/77693Answer by ab13123002https://discuss.codechef.com/questions/77642/chefgirl-editorial/77689<p>Greedy solution also passed.Why so?</p>ab13123002Mon, 14 Dec 2015 19:28:31 +0530https://discuss.codechef.com/questions/77642/chefgirl-editorial/77689Answer by xariniov9https://discuss.codechef.com/questions/77642/chefgirl-editorial/77688<p>This problem probably had weak test data, i don't know why, i submitted a wrong solution and it was partially accepted for 30 pts.</p>
<p>It just failed on two tasks of the last subtask.</p>xariniov9Mon, 14 Dec 2015 19:20:39 +0530https://discuss.codechef.com/questions/77642/chefgirl-editorial/77688