Questions Tagged With editorialhttps://discuss.codechef.com/tags/editorial/?type=rss&user=AnonymousBunnyquestions tagged <span class="tag">editorial</span>enTue, 01 Mar 2016 02:19:54 +0530SWPERMS - Editorialhttps://discuss.codechef.com/questions/79746/swperms-editorial<p></p><h2>Problem link:</h2> <a href="https://www.codechef.com/IPC15P3A/problems/SWPERMS">Contest</a> <br> <a href="https://www.codechef.com/problems/SWPERMS">Practice</a> <p></p>
<p></p><h2>PROBLEM:</h2><p></p>
<p>A permutation <b>P= (p[1], p[2], ..., p[n])</b> of <b>(1, 2, ..., n)</b> is written on a blackboard. You have <b>m</b> pairs of integers <b>(x_i, y_i)</b>. At any stage you can choose a pair <b>(x, y)</b> and swap the values of <b>p[x]</b> and <b>p[y]</b> (note that <b>P</b> is still a permutation after this operation). Initially <b>P= (1, 2, ..., n)</b>. Find the number of different permutations you can obtain after finite number of operations.
<br><br> </p> <p> </p><h2>TL;DR:</h2> <p>
Consider an undirected graph with vertices <b>1, 2, ..., n</b> where there is an edge between <b>x</b> and <b>y</b> for each given pair <b>(x, y)</b>. Let $c_1, c_2, \cdots , c_t$ be the sizes of the connected components of this graph. The answer will be $(c_1)!\cdot (c_2)! \cdots (c_t)!$
<br> <br> </p> <p> </p><h2> FULL SOLUTION: </h2> <p>
Let's consider the graph where the vertices are labelled <b>1, 2, ..., n</b> and pairs are edges. Note that swapping a pair <b>(x, y)</b> is equivalent to switching the labels of the vertices across the corresponding edge. <br> <br>
<b>Observation 1:</b> If there is no path from <b>u</b> to <b>v</b> in this graph, it is not possible to get a permutation <b>P</b> where <b>P[u]= v</b>. <br>
<b>Proof:</b> Suppose otherwise that it is possible to apply the swaps in some order that the label of vertex <b>u</b> is at the position of vertex <b>v</b> . Let $ t_1, t_2, ..., t_k$ be the successive vertices with which <b>u</b> was swapped- this means the edges $u-t_1, t_1-t_2, \cdots , t_{k-1}-t_k$ and $t_k-v$ are all present in our graph, i.e. there is a path from <b>u</b> to <b>v</b>. Contradiction. <br> <br></p>
<p>From observation 1, we find out that if <b>u</b> and <b>v</b> are in different connected components their positions cannot be interchanged. We can now treat each connected component separately. Let $f(i)$ be the number of ways the <b>i</b>'th component can be permuted, then the answer will be simply $f(1) \cdot f(2) \cdots f(t)$ where <b>t</b> is the number of connected components.</p>
<p>Now we shall prove that all possible permutations of a component can be obtained after finitely many operations, i.e. all $k!$ permutations of a connected component of size <b>k</b> can be attained. Note that this is equivalent to proving that if the graph is connected, all $n!$ permutations are achievable. <br> <br></p>
<p><b>Claim:</b> If the graph is connected, all permutations of <b>1, 2, ..., n</b> can be obtained. <br>
<b>Proof:</b> There are probably multiple ways to prove this. Here's a simple one. We'll prove that for all <b>u≠v</b>, it is possible to apply the swaps in such a way that the positions of all other elements are unchanged and those of <b>u</b> and <b>v</b> are interchanged. Since the graph is connected, there exists a simple path $t_1, t_2, ..., t_k$ from <b>u</b> to <b>v</b>. Apply the operations $u-t_1, t_1-t_2, ...., t_{k-1}-t_k, t_k-v$ - this brings the label of <b>u</b> to the position of <b>v</b> and the label of <b>v</b> to the position of $t_k$. Apply the operations $t_k-t_{k-1}, t_{k-1}-t_{k-2}, ..., t_1-u$ again- now all other labels are at their original positions and those of <b>u</b> and <b>v</b> were interchanged. Thus we can always say <b>(u, v)</b> is one of the pairs given to us (even though it isn't)- because there exists a sequence of allowed operations which has the exact same effect. Now we can simply claim to have all $\binom{n}{2}$ pairs available and it's easy to get to the conclusion. <br> <br></p>
<p>This claim shows that the number of permissible permutations of the <b>i</b>'th connected component is $(c_i)!$ where $c_i$ is its size. Thus, the answer is $(c_1)! \cdot (c_2) ! \cdots (c_t)!$ where <b>t</b> is the number of connected components. This can be found in <b>O(m+n)</b> with a plain dfs.</p>AnonymousBunnyTue, 01 Mar 2016 01:58:10 +0530https://discuss.codechef.com/questions/79746/swperms-editorialeditorialad-hocipc15p3aswpermsswpermeasyGROADS- Editorialhttps://discuss.codechef.com/questions/79749/groads-editorial<p></p><h2>Problem link:</h2> <a href="https://www.codechef.com/IPC15P3A/problems/GROADS">Contest</a> <br> <a href="https://www.codechef.com/problems/GROADS">Practice</a> <p></p>
<p></p><h2>PROBLEM:</h2><p></p>
<p>Given an unweighted undirected graph, an edge <b>u-v</b> is called interesting iff for all other vertices <b>w</b>, <b>w</b> is connected to either <b>u</b> or <b>v</b> (or maybe both). Find the number of interesting edges. </p>
<p></p> <p> </p><h2>TL;DR:</h2> <p> </p>
<p>At least one of the vertices in any interesting edge must have degree $\geq n/2$ where <b>n</b> is the total number of vertices, and the number of such vertices is pretty small.
<br> </p> <p> </p><h2> FULL SOLUTION: </h2> <p></p>
<p>Let's see how to find the number of interesting edges passing through a fixed vertex <b>v</b> in <b>O(m+n)</b>. Make an array <b>cnt[1 ... n]</b> where <b>cnt[i]=0</b> for all <b>i</b> initially. For each vertex <b>u≠v</b> which is not a neighbor of <b>v</b>, add 1 to <b>cnt[w]</b> for all <b>w</b> that is a neighbor of <b>u</b>. After this is done, <b>cnt[i]</b> will store the number of non-neighbors of <b>v</b> adjacent to <b>i</b>. Now note that in an interesting edge <b>u-v</b>, <b>u</b> must be connected to all vertices <b>v</b> isn't connected to, so <b>u-v</b> will be interesting iff <b>cnt[i]= n-1-degree(v)</b>. Unfortunately we cannot do this for every vertex because that could take up to <b>O(n^2)</b> time. <br> <br></p>
<p><b>Observation:</b> If <b>u-v</b> is an interesting edge, the degree of at least one of <b>u</b> and <b>v</b> is $\geq n/2$. <br>
<b>Proof:</b> If the degrees of <b>u</b> and <b>v</b> are both less than n/2, they are adjacent to less than $n/2+n/2= n$ vertices in total, so this edge cannot be interesting.
<br> <br>
The key fact now is that the number of vertices with degree $\geq n/2$ is quite small: in fact it's at most $4m/n$ (otherwise the sum of degrees would exceed $4m/n \cdot n/2= 2m$). Since $n(n-1)/2\geq m$, we have $n \geq O(\sqrt{m}) \implies m/n \leq O(\sqrt{m})$. This gives us a simple $O((m+n)\sqrt{m})$ solution: iterate over all vertices with degree $\geq n/2$, find the number of interesting edges passing through this vertex and add it to the answer. You must be careful about double counting some of the edges (or you could just insert the edges in a set and print the size of the set).</p>AnonymousBunnyTue, 01 Mar 2016 02:19:54 +0530https://discuss.codechef.com/questions/79749/groads-editorialipc15p3agraphsgroadseasyeditorial