Answers to: CHEFCCYL - Editorialhttps://discuss.codechef.com/questions/109131/chefccyl-editorial<p>Ah, I could have used the <code>[hid</code> <code>e][/h</code> <code>ide]</code> function if I knew it earlier. This would make editorials clearer, I think.</p>
<h1>PROBLEM LINK:</h1>
<p><a href="http://www.codechef.com/problems/PROBLEMCODE">Practice</a></p>
<p><a href="http://www.codechef.com/CONTESTCODE/problems/PROBLEMCODE">Contest</a></p>
<p><strong>Author:</strong> <a href="http://www.codechef.com/users/author_nick">Full name</a></p>
<p><strong>Tester:</strong> <a href="http://www.codechef.com/users/tester_nick">Full name</a></p>
<p><strong>Editorialist:</strong> <a href="http://www.codechef.com/users/editorialist_nick">Full name</a></p>
<h1>DIFFICULTY:</h1>
<p>CAKEWALK, SIMPLE, EASY, MEDIUM or HARD.
Intermediate levels like SIMPLE-EASY, EASY-MEDIUM, MEDIUM-HARD are also possible.</p>
<h1>PREREQUISITES:</h1>
<p>Greedy, DP, Math etc. Ideally with the links to Wikipedia</p>
<h1>PROBLEM:</h1>
<div class="hidden-block"> <div class="hide-bar view">View Content</div> <div class="hide-bar hide" style="display:none;">Hide Content</div> <div class="hidden-content" style="display:none;">
<p>There are $N$ cycles(some kind of weighted undirected graphs) and $N$ additional edges. The $i$-th additional edge connects some node on the $i$-th cycle and some node on the $(i+1)$-th cycle. Specially, the $N$-th additional edge connects some node on the $N$-th cycle and som node on the $1$-st cycle. Every edge has a weight. You need to answer $Q$ queries, each query asks you the length of the shortest path between some two nodes.</p>
</div></div>
<h1>QUICK EXPLANATION:</h1>
<p>Let's call the endpoints of additional edges "keypoint"s. The topology of keypoints form a cycle, so we can handle distance queries of keypoints quickly. For a general query, let's say it's from vertex $v_1$ on cycle $c_1$ to vertex $v_2$ on cycle $c_2$. The path goes through some keypoint $k_1$ on cycle $c_1$ and some $k_2$ on cycle $c_2$. Since every cycle has at most $2$ keypoints, we enumerate $k_1$ and $k_2$, and thus answer queries on constant time.</p>
<h1>EXPLANATION:</h1>
<h2>Subtask 1</h2>
<p>This is a shortest path problem on a graph with $M=A_1+A_2+\dots+A_N$ vertices and $M+1$ edges. We can run <a href="https://en.wikipedia.org/wiki/Dijkstra's_algorithm">Dijkstra's Algorithm</a> for each query. The time complexity for heap-optimized Dijkstra's Algorithm is $O(M\log M)$. So total complexity is $O(QM\log M)$.</p>
<h2>Subtask 2</h2>
<h3>Querying on one cycle</h3>
<p>Consider the easier problem: you have one cycle and you want to answer distance queries. Let's number the vertices $1,2,\dots,N$, and suppose the cycle is $1-2-3-\dots-N-1$. For any $i,j(i < j)$, the only simple paths between $i,j$ are:</p>
<ul>
<li>$i\to (i+1)\to(i+2)\to\dots\to j$, length $l_1$;</li>
<li>$i\to (i-1)\to\dots\to 1\to N\to (N-1)\to\dots\to (j+1)\to j$, length $l_2$.</li>
</ul>
<p><img alt="The two paths" src="https://sept17.discuss.codechef.com/upfiles/image3_X6GihEE.png"></p>
<p>Let's precompute $d_i$ as the length of path $1\to 2\to\dots\to i$. Then $l_1=d_j-d_i$. Since $l_2+l_1$ is the length of the whole cycle, $l_2$ can be easily calculated, too. We return the smaller number between $l_1$ and $l_2$, and answer the query in $O(1)$ time.</p>
<h3>Querying on keypoints</h3>
<p>Let's call the endpoints of additional edges "keypoint"s. Consider how to answer distance queries between keypoints. We construct a new graph $C$ whose vertices are only the keypoints. For two keypoints:</p>
<ul>
<li>if they are connected by an additional edge, we add this edge to $C$;</li>
<li>if they are in the same cycle, we query that cycle and get their distance $d$ in the cycle, then connect them with an edge of weight $d$.</li>
</ul>
<p><img alt="Cycle graph $C$" src="https://sept17.discuss.codechef.com/upfiles/image4_Kjhmsb9.png"></p>
<p>The resulting graph $C$ is a cycle: every vertex has degree $2$ and $C$ is connected. Thus we can easily handle distance queries on $C$. Also, $C$ preserves distances on the original graph. So we can answer distance queries about endpoints in $O(1)$ time.</p>
<h3>The final solution</h3>
<p>First, using the above algorithms we can support distance queries on one cycle and on keypoints.</p>
<p>Suppose there is a query $(V_1,C_1,V_2,C_2)$. Since $C_1\ne C_2$, their shortest path must pass through some keypoint in cycle $C_1$, suppose it's $k_1$; it also passes through some keypoint in cycle $C_2$, say $k_2$. Then the shortest path has length $dis(V_1,k_1)+dis(k_1,k_2)+dis(k_2,V_2)$, and the smallest this value among all $(k_1,k_2)$'s is the answer. The three $dis()$'s can be obtained in $O(1)$ time. Each cycle has at most $2$ keypoints, so there are at most $4$ pairs of $(k_1,k_2)$ that we need to enumerate.</p>
<p>The time complexity is $O(Q+M)$, where $M=A_1+A_2+\dots+A_N$.</p>
<h1>AUTHOR'S AND TESTER'S SOLUTIONS:</h1>
<p>Author's solution can be found [here][333].
Tester's solution can be found [here][444].</p>
<h1>RELATED PROBLEMS:</h1>
<p>[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</p>enWed, 14 Nov 2018 05:54:39 -0000